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
Python short recursive solution.

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

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.

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)

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)

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


@caikehe Beautiful solution! It took me a while to figure out that in your solution
left_preorder
andright_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 leftsubtree 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