Recursive Python solution - 72ms (94.5%)


  • 0
    S

    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):
                my_dict[v]=i
            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.