This approach uses recursion and a HashMap to efficiently construct the binary tree. The key insight is that the last element in the postorder array is the root node. This node's index in the inorder array can be found using a HashMap, allowing constant time access during recursive calls.
Time Complexity: O(n), where n is the number of nodes. Each node is visited once.
Space Complexity: O(n), where n is the number of nodes for storing the map and recursion stack.
1import java.util.HashMap;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 private int post_idx;
12 private int[] postorder;
13 private HashMap<Integer, Integer> idx_map = new HashMap<>();
14
15 public TreeNode buildTree(int[] inorder, int[] postorder) {
16 this.postorder = postorder;
17 post_idx = postorder.length - 1;
18
19 int idx = 0;
20 for (int val : inorder)
21 idx_map.put(val, idx++);
22
23 return helper(0, inorder.length - 1);
24 }
25
26 private TreeNode helper(int in_left, int in_right) {
27 if (in_left > in_right)
28 return null;
29
30 int root_val = postorder[post_idx];
31 TreeNode root = new TreeNode(root_val);
32 post_idx--;
33
34 int index = idx_map.get(root_val);
35 root.right = helper(index + 1, in_right);
36 root.left = helper(in_left, index - 1);
37
38 return root;
39 }
40}In this Java solution, a recursive helper function is used in conjunction with a HashMap to efficiently locate indices of given values. The hashmap helps in quick lookup of indices, speeding up the recursive construction.
This approach builds the tree using an iterative method with a stack. It tracks nodes that need a child and assigns them accordingly. It takes advantage of the tree properties in the postorder and inorder arrays for efficient traversal and node placement.
Time Complexity: O(n), where n is the number of nodes. Every element is seen once.
Space Complexity: O(n), where n is the number of nodes to account for the stack and tree storage.
1function TreeNode(val, left = null, right = null) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7var buildTree = function(inorder, postorder) {
8 if (!postorder.length) return null;
9
10 let root = new TreeNode(postorder[postorder.length - 1]);
11 let stack = [root];
12 let inorderIndex = inorder.length - 1;
13
14 for (let i = postorder.length - 2; i >= 0; i--) {
15 let node = stack[stack.length - 1];
16 if (node.val !== inorder[inorderIndex]) {
17 node.right = new TreeNode(postorder[i]);
18 stack.push(node.right);
19 } else {
20 while (stack.length && stack[stack.length - 1].val === inorder[inorderIndex]) {
21 node = stack.pop();
22 inorderIndex--;
23 }
24 node.left = new TreeNode(postorder[i]);
25 stack.push(node.left);
26 }
27 }
28
29 return root;
30};This JavaScript solution uses a stack to iteratively build the tree. It maintains nodes that need children and assigns nodes based on whether they are different from the current inorder node. Nodes are popped from the stack when they match inorder traversal to handle left children appropriately.