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