Python short recursive solution.


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

  • 6
    Z

    Hey caikehe, thank you for the great and clean code.

    My code had MLE problem, and used the same algorithm as you. So I simplified my code using yours as model

    My code ended up this (MLE):

    if inorder:
            node = TreeNode(preorder[0])
            node_index = inorder.index(preorder[0])
            l_len = len(inorder[:node_index])
            node.left = self.buildTree(preorder[1:l_len+1], inorder[0:l_len])
            node.right = self.buildTree(preorder[l_len+1:], inorder[l_len+1:])
            return node
    

    but this worked (more similar like yours):

    if inorder:
            node = TreeNode(preorder[0])
            node_index = inorder.index(preorder[0])
            preorder.pop(0)
            l_len = len(inorder[:node_index])
            node.left = self.buildTree(preorder, inorder[0:l_len])
            node.right = self.buildTree(preorder, inorder[l_len+1:])
            return node
    

    I have been careful about the passing data in recursion, and usually encounter no problem in other questions.

    Can you explain why I have to pass a popped "preorder", and cannot process "preorder" like "inorder"?

    Thank you!

    Answer: it is not a slicing error, it is because the slicing creates new lists, hence the space usage for preorder is doubled in each recursion


  • 4
    C

    The slice operation usually costs k space when you slice like list[:k], because you create a new list whose size is k. If you want to get rid of MLE, a normal way is using indexes, which means you can input the lower and upper bound indexes as parameters. For instance, the above example can call a helper function like: buildTreeHelper(preorder, inorder, lower1, upper1, lower2, upper2), lower1 and upper1, lower2 and upper2 are corresponding to the preorder and inorder indexes respectively.


  • 2
    G

    Preorder: [root, left nodes, right nodes],
    Inorder: [left nodes, root, right nodes].
    With preorder.pop(0) executed for each
    node.left = self.buildTree(preorder[1:l_len+1], inorder[0:l_len]) and its recursive steps, we can guarantee that left nodes are all popped out in the preorder list and it is ready for
    root.right = self.buildTree(preorder, inorder[ind+1:]).
    That's why it works and it helps in avoiding building new sliced preorder list, but the better/clearer way to do it should be using a helper function like
    buildTreeHelper(preorder, inorder, preLower, preUpper, inLower, inUpper)


  • 0
    J
    This post is deleted!

  • 1

    Nice!!! How did you come up this idea?


  • 0

    This is short as expected but it is slow because too many pop, slice and index operations.


  • 0
    L

    Slightly more optimal solution, but the index check makes this a slow solution. I'm sure there's a better solution without checking index of the inorder list

        def buildTree(self, preorder, inorder):
            def build(preorder,inorder):
                if inorder:
                    ind = inorder.index(preorder.pop())
                    root = TreeNode(inorder[ind])
                    root.left = build(preorder, inorder[ind+1:])
                    root.right = build(preorder, inorder[0:ind])
                    return root
            preorder.reverse()
            inorder.reverse()
            return build(preorder,inorder)

  • 0

    @livelearn the inorder list doesn't have to be reversed, reversing the preorder list is enough.


  • 0
    L

    @skywalker_tju lol good point


  • 8

    0_1486248259663_Screenshot 2017-02-04 17.44.08.png
    Looking at preorder traversal, the first value (node 1) must be the root.
    Then, we find the index of root within in-order traversal, and split into two sub problems.


  • 0
    P

    @caikehe Beautiful solution! It took me a while to figure out that in your solution left_preorder and right_preorder are not being computed separately even though they could (to make the code more understandable). preorder is a mutable object (list) and since you are building the left-subtree first, it will just extract out it's elements first before the right subtree recursive call uses it. Just beautiful!

    My solution (very similar to yours, only difference being that I explicitly computed the left_preorder and right_preorder lists before doing the recursive calls taking up more memory):

        def buildTree(self, preorder, inorder):
      
            if len(inorder) == 0:
                return None
    
            if len(inorder) == 1:
                return TreeNode(preorder[0])
            
            rval = preorder[0]
            root = TreeNode(rval)
            
            inorder_rval_index = inorder.index(rval)
            left_inorder = inorder[:inorder_rval_index]
            right_inorder = inorder[inorder_rval_index+1:]
            left_preorder = preorder[1: len(left_inorder) + 1]
            right_preorder = preorder[1 + len(left_preorder):]
            
            root.left = self.buildTree(left_preorder, left_inorder)
            root.right = self.buildTree(right_preorder, right_inorder)
            
            return root
    

Log in to reply
 

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