Construct Binary Tree from Inorder and Postorder Traversal

Problem Id: 106 Difficulty: Medium Tag: Array Tag: Tree Tag: Depth-first Search


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[2] + [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