# 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
A Python recursive solution


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

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+index1, pleft, pleft + index1) root_right = build_tree(ileft+ index +1, iright, pleft+ index, pright1) root.left = root_left root.right = root_right return root ileft = 0 iright = inorder_len1 pleft = 0 pright = postorder_len1 root = build_tree(ileft, iright, pleft, pright) 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?

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 "lefthalf" 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 leftgoing algorithm on paper.
It follows from this that you'll need to go left first when building from a preorder list.

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