A Python recursive solution

• ``````# 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``````

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

• 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)

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

• 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.

• 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``````

• 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)

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

• 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``````

• @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?

• @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.

• This post is deleted!

• 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
``````

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