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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def buildTree(self, inorder, postorder):
9 idx_map = {val: idx for idx, val in enumerate(inorder)}
10 self.post_idx = len(postorder) - 1
11
12 def helper(in_left, in_right):
13 if in_left > in_right:
14 return None
15
16 root_val = postorder[self.post_idx]
17 root = TreeNode(root_val)
18 self.post_idx -= 1
19
20 index = idx_map[root_val]
21 root.right = helper(index + 1, in_right)
22 root.left = helper(in_left, index - 1)
23
24 return root
25
26 return helper(0, len(inorder) - 1)This Python solution employs a recursive helper function to build the tree. The postorder index is decremented each time a new root is established, while the hashmap provides constant-time access to any given node's inorder index.
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.