CONSTRUCT BINARY TREE FROM INORDER AND POSTORDER TRAVERSAL


  • 0
    A
    # Space: O(n)
    #
    # Given inorder and postorder traversal of a tree, construct the binary tree.
    #
    # Note:
    # You may assume that duplicates do not exist in the tree.
    #
    
    # Definition for a  binary tree node
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    class Solution:
        # @param inorder, a list of integers
        # @param postorder, a list of integers
        # @return a tree node
        def buildTree(self, inorder, postorder):
            lookup = {}
            for i, num in enumerate(inorder):
                lookup[num] = i
            return self.buildTreeRecu(lookup, postorder, inorder, len(postorder), 0, len(inorder))
    
        def buildTreeRecu(self, lookup, postorder, inorder, post_end, in_start, in_end):
            if in_start == in_end:
                return None
            node = TreeNode(postorder[post_end - 1])
            i = lookup[postorder[post_end - 1]]
            node.left = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1 - (in_end - i - 1), in_start, i)
            node.right = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1, i + 1, in_end)
            return node
    
    if __name__ ==  "__main__":
        inorder = [2, 1, 3]
        postorder = [2, 3, 1]
        result = Solution().buildTree(inorder, postorder)
        print result.val
        print result.left.val
        print result.right.val
    

Log in to reply
 

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