Preorder only solution in Python


  • 0
    R

    By the definition of BST, when we serialize it into a preorder string. Root.val will always at the head of string. Right substree will start at j which subjects to data[j] > data[0]. Then construct left and right subtree recursively easily.

    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            if not root:
                return ''
            return '#'.join([str(root.val), self.serialize(root.left), self.serialize(root.right)])
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            return self._deserialize([int(n) for n in data.split('#') if n])
            
        def _deserialize(self, data):
            if not data:
                return None
            root = TreeNode(data[0])
            j = 1
            while j < len(data):
                if data[j] > data[0]:
                    break
                j += 1
            root.left = self._deserialize(data[1:j])
            root.right = self._deserialize(data[j:])
            return root
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.