Recursive Python solution - 72ms (94.5%)

  • 0

    We know that the last node in Postorder is the root of the tree. So we start there and recursively populate its right and left children (note that we populate right first and then left, because while coming backwards in Postorder, right comes before left).

    class Solution(object):
        def buildTree(self, inorder, postorder):
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            my_dict = {}    #Hashmap to store inorder index for fast retrievals
            for i,v in enumerate(inorder):
            self.post_curr = len(postorder)-1
            def helper(postorder,start,end,my_dict):
                if start>end or self.post_curr<0:
                    return None
                root = TreeNode(postorder[self.post_curr])
                self.post_curr = self.post_curr-1
                ind = my_dict[root.val]
                root.right = helper(postorder,ind+1,end,my_dict)
                root.left = helper(postorder,start,ind-1,my_dict)
                return root
            return helper(postorder,0,len(inorder)-1,my_dict)

Log in to reply

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