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. For example:

Example 1:

inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

Expected Output: [3,9,20,null,null,15,7]

Example 2:

inorder = [-1], postorder = [-1]

Expected Output: [-1]

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Create a hashmap to store the indices of inorder elements for quick access.
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        
        # Index to track the current element in postorder (start from the end).
        postorder_index = len(postorder) - 1

        def build_subtree(left, right):
            nonlocal postorder_index  # Allow modification of the outer scope variable

            # Base case: If the subtree is empty.
            if left > right:
                return None

            # Create the root node with the last element from postorder.
            root_val = postorder[postorder_index]
            root = TreeNode(root_val)

            # Find the index of the root value in inorder.
            inorder_index = inorder_map[root_val]

            # Decrement the postorder index (move to the next root).
            postorder_index -= 1

            # Recursively build the right subtree and then the left subtree.
            # Note: Right subtree is built first because of the postorder traversal.
            root.right = build_subtree(inorder_index + 1, right)
            root.left = build_subtree(left, inorder_index - 1)

            return root

        # Start building the tree from the entire inorder list.
        return build_subtree(0, len(inorder) - 1)

Explanation:

The solution constructs a binary tree from its inorder and postorder traversals. The key idea is to use the last element in the postorder array as the root of the current (sub)tree. By finding this root's index in the inorder array, we can divide the inorder array into left and right subtrees.

1. Hashmap for Inorder Indices: A hashmap inorder_map is created to store the indices of elements in the inorder array. This allows for quick access to the index of any element in inorder.
2. Postorder Index: The postorder_index variable keeps track of the current element being processed in the postorder array. It starts from the end of the array because the last element in postorder is the root of the tree.
3. Recursive Subtree Building: The build_subtree function is a recursive function that builds the tree. It takes the left and right boundaries of the inorder array as input. Here's how it works:
   • Base Case: If the left boundary is greater than the right boundary, it means there are no more nodes to process, so the function returns None.
   • Root Creation: It creates a new TreeNode using the value at the postorder_index in the postorder array. This is the root of the current subtree.
   • Inorder Index Lookup: It finds the index of the root's value in the inorder array using the inorder_map. This index divides the inorder array into left and right subtrees.
   • Postorder Index Decrement: It decrements the postorder_index to move to the next root in the postorder array.
   • Recursive Calls: It recursively calls build_subtree to build the right subtree and then the left subtree. The right subtree is built first because of the order of nodes in the postorder traversal.
4. Initial Call: The buildTree function calls build_subtree with the initial left and right boundaries of the inorder array (0 and len(inorder) - 1).

Example:

Given inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]:

1. The last element in postorder is 3, which is the root of the tree.
2. The index of 3 in inorder is 1, so the left subtree is [9] and the right subtree is [15,20,7].
3. The next element in postorder (from right to left) is 20, which is the root of the right subtree.
4. The index of 20 in inorder is 3, so the left subtree of 20 is [15] and the right subtree is [7].
5. The process continues recursively until the entire tree is built.

Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because each node is visited once.
• Space Complexity: O(N) in the worst case. This is due to the recursion stack, which can be as large as the height of the tree. In the worst-case scenario (skewed tree), the height can be N. Additionally, the inorder_map stores N elements, contributing to the space complexity.