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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode BuildTree(int[] inorder, int[] postorder) {
10 if (postorder.Length == 0) return null;
11
12 TreeNode root = new TreeNode(postorder[postorder.Length - 1]);
13 Stack<TreeNode> stack = new Stack<TreeNode>();
14 stack.Push(root);
15
16 int inorderIndex = inorder.Length - 1;
17
18 for (int i = postorder.Length - 2; i >= 0; i--) {
19 TreeNode node = stack.Peek();
20 if (node.val != inorder[inorderIndex]) {
21 node.right = new TreeNode(postorder[i]);
22 stack.Push(node.right);
23 } else {
24 while (stack.Count > 0 && stack.Peek().val == inorder[inorderIndex]) {
25 node = stack.Pop();
26 inorderIndex--;
27 }
28 node.left = new TreeNode(postorder[i]);
29 stack.Push(node.left);
30 }
31 }
32
33 return root;
34 }
35}This C# solution employs an iterative strategy using a stack to keep track of nodes waiting for children. It efficiently handles both left and right placements by ensuring stack-popped nodes are aligned with the inorder positions.