A Python recursive solution


  • 28
    G
    # 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
        # 12:00
        def buildTree(self, inorder, postorder):
            if not inorder or not postorder:
                return None
            
            root = TreeNode(postorder.pop())
            inorderIndex = inorder.index(root.val)
    
            root.right = self.buildTree(inorder[inorderIndex+1:], postorder)
            root.left = self.buildTree(inorder[:inorderIndex], postorder)
    
            return root

  • 0
    I

    Wow, this is so clever!! Can you share how did you figure this out? Any hint or idea drives you to this neat solution?


  • 1
    G

    It is well explained here http://fisherlei.blogspot.com/2013/01/leetcode-construct-binary-tree-from.html, I used array slice instead of index though (to make the code a little bit cleaner)


  • 0
    M

    I have the exactly same answer, but why I got "The Memory Limit Exceeded"?


  • 0
    G

    probably because OJ updated its test cases, I think you can pass OJ by changing the list slice to actually pass the index for each iteration to reduce the memory usage.


  • 0
    A

    The following is my code, which takes fewer memory.

    class Solution:
        # @param {integer[]} inorder
        # @param {integer[]} postorder
        # @return {TreeNode}
        def buildTree(self, inorder, postorder):
            if inorder is None or postorder is None:
                return
    
            inorder_len = len(inorder)
            postorder_len = len(postorder)
    
            if inorder_len != postorder_len:
                return
    
    
            if inorder_len == 0:
                return
    
            def build_tree(ileft, iright, pleft, pright):
                if ileft == iright:
                    return TreeNode(inorder[ileft])
    
                if iright < ileft or pleft > pright:
                    return
    
                root_num = postorder[pright]
                root = TreeNode(root_num)
    
                # index = 0
                # while inorder[index+ileft] != root_num and index <= iright:
                #     index += 1
                index = inorder.index(root_num)
                index = index - ileft
    
                root_left = build_tree(ileft, ileft+index-1, pleft, pleft + index-1)
                root_right = build_tree(ileft+ index +1, iright, pleft+ index, pright-1)
    
                root.left = root_left
                root.right = root_right
    
                return root
    
            ileft = 0
            iright = inorder_len-1
            pleft = 0
            pright = postorder_len-1
    
    
            root = build_tree(ileft, iright, pleft, pright)
    
            return root

  • 0
    L

    inorder[inorderIndex+1:] will create a new list instance. That's why you get "The Memory Limit Exceeded". try this: self._build_tree(inorder, low_in, high_in, postorder, low_post, high_post)


  • 0
    F

    So nice! modify the originally node list makes life easy!


  • 0
    L

    My solution

            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
    C

    @livelearn
    why switch these two:

    root.right=self.buildTree(inorder[ind+1:],postorder)
    root.left=self.buildTree(inorder[:ind],postorder)
    

    into:

    root.left=self.buildTree(inorder[:ind],postorder)
    root.right=self.buildTree(inorder[ind+1:],postorder)
    

    will result in an error?


  • 1
    S

    @CeltRay001

    When building from a postorder list, you have to go right before you go left. If you manually work through the algorithm where you're going left first, you'll see where the error arises from. When you go left, you're slicing the inorder list as inorder[:ind]. This "left-half" of the inorder list will not contain the node you just popped from the postorder array. That's because as you keep popping from the postorder list, you'll hit the right children first, so you need to go right and place those in your tree before moving on to the left.

    Again, it's best understood if you work through each iteration of the left-going algorithm on paper.

    It follows from this that you'll need to go left first when building from a preorder list.


  • 0
    C
    This post is deleted!

  • 1
    C

    Here is my solution

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

Log in to reply
 

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