Recursive with HashMap
Intuition
The first element in the preorder array is always the root of the current subtree. By finding this root's position in the inorder array, we can determine which elements belong to the left subtree (everything before the root in inorder) and which belong to the right subtree (everything after). We use a hash map to look up positions in the inorder array in O(1) time, and a pointer to track our position in the preorder array. The left subtree is built first because preorder visits left before right.
Algorithm
- Build a hash map from each value in inorder to its index for O(1) lookup.
- Initialize a preorder index pointer starting at 0.
- Define a recursive function that takes the current inorder range (left, right).
- If left > right, return null (empty subtree).
- The current root value is preorder[preorderIndex]. Increment the pointer.
- Create a new node with this value.
- Find the root's index in inorder using the hash map.
- Recursively build the left subtree with the inorder range (left, rootIndex - 1).
- Recursively build the right subtree with the inorder range (rootIndex + 1, right).
- Return the node.
Time
O(n)SpaceO(n)Code (C++ · Java · Python · Go)
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
int preIdx = 0;
return build(preorder, inorderMap, preIdx, 0, inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& preorder, unordered_map<int, int>& inorderMap,
int& preIdx, int left, int right) {
if (left > right) return nullptr;
int rootVal = preorder[preIdx++];
TreeNode* root = new TreeNode(rootVal);
int mid = inorderMap[rootVal];
root->left = build(preorder, inorderMap, preIdx, left, mid - 1);
root->right = build(preorder, inorderMap, preIdx, mid + 1, right);
return root;
}
};class Solution {
private int preIdx = 0;
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int left, int right) {
if (left > right) return null;
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
int mid = inorderMap.get(rootVal);
root.left = build(preorder, left, mid - 1);
root.right = build(preorder, mid + 1, right);
return root;
}
}def buildTree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
inorder_map = {val: idx for idx, val in enumerate(inorder)}
pre_idx = [0]
def build(left, right):
if left > right:
return None
root_val = preorder[pre_idx[0]]
pre_idx[0] += 1
root = TreeNode(root_val)
mid = inorder_map[root_val]
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)func buildTree(preorder []int, inorder []int) *TreeNode {
inorderMap := make(map[int]int)
for i, v := range inorder {
inorderMap[v] = i
}
preIdx := 0
var build func(int, int) *TreeNode
build = func(left, right int) *TreeNode {
if left > right {
return nil
}
rootVal := preorder[preIdx]
preIdx++
root := &TreeNode{Val: rootVal}
mid := inorderMap[rootVal]
root.Left = build(left, mid-1)
root.Right = build(mid+1, right)
return root
}
return build(0, len(inorder)-1)
}