106. Construct Binary Tree from Inorder and Postorder Traversal

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
• topics: Tree

Description

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Intuition

Same Idea and algorithm as in 105. Construct Binary Tree from Preorder and Inorder Traversal, but from the end and building the right subtree first

Code

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
 
        def array_to_tree(left, right):
            nonlocal postorder_index
            # if there are no elements to construct the tree
            if left > right:
                return None
 
            # select the postorder element as the root and decrement it
            root_value = postorder[postorder_index]
            root = TreeNode(root_value)
 
            postorder_index -= 1
 
            # build left and right subtree
            # excluding inorder_index_map[root_value] element because it's the root
            root.right = array_to_tree(postorder_index_map[root_value] + 1, right)
            root.left = array_to_tree(left, postorder_index_map[root_value] - 1)
            
 
            return root
 
        postorder_index = len(postorder) - 1
 
        # build a hashmap to store value -> its index relations
        postorder_index_map = {}
        for index, value in enumerate(inorder):
            postorder_index_map[value] = index
 
        return array_to_tree(0, len(postorder) - 1)