This is almost the same as problem 105.
Let's assume the last value in postorder is a. Then a must be the root node of the tree. Besides, the inorder could be splitted into 3 part left + [a] + right. And also preorder could be splitted into 3 part left2 + right + [a] based on the length of left and right. left is the inorder of the left subtree, and left2 is the postorder of the left subtree. Right subtree is the same.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: if len(inorder) == 0: return None node = TreeNode(postorder[-1]) mid = inorder.index(node.val) node.left = self.buildTree(inorder[:mid], postorder[:mid]) node.right = self.buildTree(inorder[mid + 1:], postorder[mid:-1]) return node