Problem Explanation

We're given the inorder and postorder traversals of a binary tree without duplicates, and asked to construct the binary tree from these traversals.

Binary tree traversals provide sequences listing the nodes of the tree. For instance, the inorder traversal lists nodes from left to right ("in order"). The postorder traversal first lists the left subtree, then the right subtree, then the root.

Given the inorder: [9,3,15,20,7] and the postorder: [9,15,7,20,3] we're meant to reconstruct the tree:

1
2
3    3
4   / \
5  9  20
6    /  \
7   15   7

Solution Approach

Let's start with the following inorder and postorder arrays:

Inorder: [9,3,15,20,7]
Postorder: [9,15,7,20,3]

The solution approach is based on the fact that the last element in the postorder array is the root of the tree. In this case, 3 is the root of the tree.

Also, the roots divide the left and right subtree in the inorder array. Hence in the inorder array [9,3,15,20,7], 9 is on the left subtree and [15,20,7] is on the right subtree.

The buildTree function uses these facts to construct the binary tree recursively. It creates a dictionary of indices for elements in the inorder tree for fast lookup. Then it constructs the tree using the build function which considers the arrays and their start and end indices.

Each recursive step pops the last element from the postorder list (postEnd), defines it as a root, and divides the rest of the list into two parts: elements on the left are in the left subtree and elements on the right are in the right subtree.

This recursive step is applied to both subtrees until the complete binary tree is built.

Python Solution

1
2python
3class Solution:
4    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
5        def helper(in_left=0, in_right=len(inorder)):
6            nonlocal post_idx
7            if in_left == in_right:
8                return None
9
10            root_val = postorder[post_idx]
11            root = TreeNode(root_val)
12
13            index = idx_map[root_val]
14
15            post_idx -= 1
16            root.right = helper(index+1, in_right)
17            root.left = helper(in_left, index)
18            return root
19
20        post_idx = len(postorder) - 1
21
22        idx_map = {val:idx for idx, val in enumerate(inorder)}
23        return helper()

Java Solution

1
2java
3import java.util.HashMap;
4
5public class Solution {
6    int post_idx;
7    int[] postorder;
8    int[] inorder;
9    HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
10
11    public TreeNode helper(int in_left, int in_right) {
12        if (in_left == in_right)
13            return null;
14
15        int root_val = postorder[post_idx];
16        TreeNode root = new TreeNode(root_val);
17
18        int index = idx_map.get(root_val);
19
20        post_idx--;
21
22        root.right = helper(index+1, in_right);
23        root.left = helper(in_left, index);
24        return root;
25    }
26
27    public TreeNode buildTree(int[] inorder, int[] postorder) {
28        this.postorder = postorder;
29        this.inorder = inorder;
30
31        post_idx = postorder.length - 1;
32
33        int idx = 0;
34        for (Integer val: inorder)
35            idx_map.put(val, idx++);
36        return helper(0, inorder.length);
37    }
38}

C++ Solution

1
2cpp
3class Solution {
4public:
5    unordered_map<int, int> map;
6    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
7        for(int i = 0; i < inorder.size(); i++) {
8            map[inorder[i]] = i;
9        }
10        return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
11    }
12
13    TreeNode* helper(vector<int>& inorder, int iStart, int iEnd, vector<int>& postorder, int pStart, int pEnd) {
14        if(iStart > iEnd || pStart > pEnd) return NULL;
15        TreeNode* root = new TreeNode(postorder[pEnd]);
16        int iIndex = map[postorder[pEnd]];
17        root->left = helper(inorder, iStart, iIndex - 1, postorder, pStart, pStart + iIndex - iStart - 1);
18        root->right = helper(inorder, iIndex + 1, iEnd, postorder, pStart + iIndex - iStart, pEnd - 1);
19        return root;
20    }
21};

JavaScript Solution

1
2js
3var buildTree = function(inorder, postorder) {
4    let map = new Map()
5    inorder.forEach((val, idx) => map.set(val, idx))
6    
7    let i = postorder.length - 1
8    
9    function helper(start, end){
10        if(start > end) return null
11        let val = postorder[i]
12        let idx = map.get(val)
13        i--
14        let root = new TreeNode(val)
15        root.right = helper(idx+1, end)
16        root.left = helper(start, idx-1)
17        return root
18    }
19    
20    return helper(0, inorder.length - 1)
21};

This solution creates a Map where each node value from the inorder array is a key and its index is the value, this will allow us to later locate the root of each subtree in constant time.

C# Solution

1
2csharp
3public class Solution {
4    Dictionary<int, int> inorderIndexes = new Dictionary<int, int>();
5    int[] inorder;
6    int[] postorder;
7    int postIndex;
8
9    public TreeNode BuildTree(int[] inorder, int[] postorder) {
10        this.inorder = inorder;
11        this.postorder = postorder;
12        postIndex = postorder.Length - 1;
13
14        int idx = 0;
15        foreach (int val in inorder)
16            inorderIndexes.Add(val, idx++);
17        return helper(0, inorder.Length);
18    }
19
20    public TreeNode helper(int inLeft, int inRight) {
21        if (inLeft == inRight)
22            return null;
23
24        int rootVal = postorder[postIndex];
25        TreeNode root = new TreeNode(rootVal);
26
27        int index = inorderIndexes[rootVal];
28
29        postIndex--;
30        root.right = helper(index+1, inRight);
31        root.left = helper(inLeft, index);
32        return root;
33    }
34}

The given solution follows the same logic laid out above. It includes a helper function that constructs the binary tree given the inorder and postorder arrays. This binary tree is built recursively and returned once fully formed. The solution starts by mapping the inorder array to a dictionary (for Python and C#), a Hashmap (for Java), and a Map (for JavaScript), while C++ uses an unordered_map. Each value in the inorder array becomes a key in the dictionary, and its index becomes the corresponding value. This mapping is done for efficient look-up of indices corresponding to the values in the inorder array.

In all the solutions, a counter is initialized to point to the last index of the postorder array because the last node in the postorder sequence will be the root of the tree. This counter is decremented through each recursive call as we build the tree from the root node downwards, moving towards the first node in the postorder sequence.

The helper function, which constructs the tree, is initially called with the start and end indices set to cover the entire input. If the start and end indices become equal, it means that there is no element to construct the subtree, and hence it should return null.

The root node of the binary tree is created by identifying the value using the counter in the postorder array. Using the root value, the index of this value in the inorder sequence is found. This index is used to split the inorder sequence into two parts, left and right subtree.

The helper function is then called recursively to construct the right subtree before the left subtree because we're decrementing from the end of the postorder array, following right-to-left. After constructing both subtrees, these are attached to the root node and finally, the root node is returned.

This process continues recursively until the entire tree is constructed, working all the way down from the root to the leaves. To construct the tree, we're essentially working back up from the postorder array, constructing a node and its subtrees, then passing that node back up to its parent node.

This way, we use the information provided by both arrays to recreate the original binary tree. Given the constraints of the task (unique values within the tree), this will always create the correct and only possible tree.