Construct Binary Tree from Inorder and Postorder Traversal

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Problems

Construct Binary Tree from Inorder and Postorder Traversal

We want to return the binary tree by given inorder and postorder Traversal.

Approach

Postorder is left->right->root and inorder is left->root->right, so the root of tree is the rightmost of postorder traversal and we can get to know the subtree of it by checking inorder traversal.

For example:
inorder = 9,3,15,20,7 (left->root->right)
postorder = 9,15,7,20,3 (left->right->root)

The root is 3 because it is the rightmost in postorder traversal and the left subtree is 9 and the right subtree is 15, 20, 7 because in inorder Traversal, 9 is left of 3(=root) and 15, 20, 7 is right of 3. The next root is 20, and the right subtree is 15 and the left subtree is 7.

So we are able to solve this question by repeating this process.

Solution

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(left_end, right_end):
            if left_end > right_end:
                return None

            value = postorder.pop()
            root = TreeNode(value)

            index = index_map[value]

            root.right = helper(index + 1, right_end)
            root.left = helper(left_end, index - 1)
            return root

        index_map = {val:idx for idx, val in enumerate(inorder)} 
        return helper(0, len(inorder) - 1)

Thank you for reading this article!
I always welcome your feedback, question, and idea.