Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

In the given challenge, we are provided with two integer arrays named inorder and postorder. These arrays represent the inorder and postorder traversal sequences of a binary tree, respectively. The task is to reconstruct the original binary tree from these traversal sequences. The reconstructed binary tree should mirror the structure and values present in the initial tree based on the provided traversals.

Examples

Example 1

Input:

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

Output:

[3,9,20,null,null,15,7]

Example 2

Input:

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

Output:

[-1]

Constraints

• 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.

Approach and Intuition

Recursive Method to Construct the Binary Tree

1. The key understanding here is that the last element in the postorder array represents the root of the tree. This is a defining feature of postorder traversal where a node is processed after its subtrees.

2. Knowing the root, the inorder array can be split into two parts:

   • All elements to the left of the root in the inorder array will belong to the left subtree.
   • All elements to the right of the root in the inorder array will belong to the right subtree.

3. Using the identified root from the postorder array, you can divide the inorder array into two halves at the root's position. This positional information then guides the split in the postorder array as well.

4. This process is recursive:

   • The next root will be the previous root's right neighbor in the postorder array for the right subtree.
   • Similarly, it will be the immediate previous element for the left subtree before the original root.

5. Continue this recursive division until:

   • All elements are processed.
   • The subarrays for inorder or postorder become empty which indicates that you've reached a leaf node.

6. Edge cases:

   • When the inorder and postorder arrays contain only one element. This scenario means the tree consists of a single node or a leaf node in recursive calls.

Example Walkthrough

The perspective approach can be illustrated using the provided examples:

For Example 1

• Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
• The root can be identified to be 3 from the postorder last element.
• Now, split at 3 in inorder, constructing subtrees with [9] for left, and [15,20,7] for right.
• This process will continue recursively based on the new roots identified from the postorder array.

For Example 2

• Input: inorder = [-1], postorder = [-1]
• Since there is only one element, it's straightforward. The tree will consist of a single node with value -1.

This recursive approach ensures that each element is used to correctly partition and construct subtrees accurately maintaining all binary tree properties according to the traversals provided.

Solutions

class Solution {
    int current_post_idx;
    vector<int> postorder_seq;
    vector<int> inorder_seq;
    unordered_map<int, int> val_to_index_map;
    
public:
    TreeNode* construct_subtree(int in_left, int in_right) {
        if (in_left > in_right) return NULL;
        int root_value = postorder_seq[current_post_idx];
        TreeNode* root_node = new TreeNode(root_value);
        int split_index = val_to_index_map[root_value];
        current_post_idx--;
        root_node->right = construct_subtree(split_index + 1, in_right);
        root_node->left = construct_subtree(in_left, split_index - 1);
        return root_node;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder_seq = postorder;
        this->inorder_seq = inorder;
        current_post_idx = postorder.size() - 1;
        int index_counter = 0;
        for (int value : inorder) val_to_index_map[value] = index_counter++;
        return construct_subtree(0, inorder.size() - 1);
    }
};