106. Construct Binary Tree from Inorder and Postorder Traversal

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.

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

       

    def recurse(in_start, in_end):

        if in_start > in_end:

            return None

       

        root_val = postorder.pop()

                   

        in_p = inorder_map[root_val]

       

        left_start,  left_end  = in_start, in_p-1

        right_start, right_end = in_p+1, in_end

       

        root = TreeNode(root_val)

       

        root.right = recurse(right_start, right_end)

        root.left  = recurse(left_start,  left_end)

       

        return root

       

    inorder_map = {}

    for i,e in enumerate(inorder):

        inorder_map[e] = i

    ans = recurse(0, len(inorder)-1)

    return ans