Simple Python preorder


  • 0

    In serialize step we do a preorder traversal to get the string. For reconstructing the BST, l and r are the left and right boundaries of our current array. Since it's preorder traversal, for root value A[l], once we find the first point A[mid] < A[l], we know all values from this point until the right boundary are for the right subtree, and points before that until left boundary are the left subtree.

    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            def preorder(node):
                if node:
                    res.append(str(node.val))
                    preorder(node.left)
                    preorder(node.right)
            res = []
            preorder(root)
            return " ".join(res)
            
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            def build(l, r):
                if l >= r: return None
                root = TreeNode(A[l])
                mid = l+1
                while mid < r and A[mid] < root.val: mid += 1
                root.left = build(l+1, mid)
                root.right = build(mid, r)
                return root
                
            A = map(int, data.split())
            return build(0, len(A))
    

Log in to reply
 

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