Construct Binary Tree from Inorder and Postorder Traversal

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


Intuition

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.

Solution


# 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