Python short solution (recursively).


  • 17
    C
    def buildTree(self, inorder, postorder):
        if inorder:
            ind = inorder.index(postorder.pop())
            root = TreeNode(inorder[ind])
            root.right = self.buildTree(inorder[ind+1:], postorder)
            root.left = self.buildTree(inorder[:ind], postorder)
            return root

  • 0
    P

    @caikehe

    class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            if inorder:
                ind = inorder.index(postorder.pop())
                root = TreeNode(inorder[ind])
                root.left = self.buildTree(inorder[:ind],postorder)
                root.right = self.buildTree(inorder[ind+1:],postorder)
                return root
    

    Could you help me understand why this is throwing an error ? Thank you for your help in advance.
    I guess its because in postorder we have
    left,right,middle elements so we have to first construct middle node, then right node and then left node. very concise code for both 106. Construct Binary Tree from Inorder and Postorder Traversal and 105 Construct Binary Tree from Preorder and Inorder Traversal problems


  • 0
    Z

    here is a recursive version without index, much faster, 66 ms: https://discuss.leetcode.com/topic/91582/o-n-recursive-solution-without-hashmap-nor-index


Log in to reply
 

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