Given two integer arrays preorder and inorder where preorder is the preorder traversal and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Input: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] → Output: [3,9,20,null,null,15,7]Input: preorder=[1], inorder=[1] → Output: [1]
The first element of preorder is always the root. Find its position in inorder; elements to its left form the left subtree, right form the right subtree. Recurse.
- preIndex = 0 (global counter).
- Find root = preorder[preIndex++] in inorder using a HashMap for O(1) lookup.
- Elements at inorder[0..mid-1] are left subtree, inorder[mid+1..] are right subtree.
- Recurse: build left subtree, then right subtree.
import java.util.*;
class Solution {
int preIdx = 0;
Map<Integer, Integer> inMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int lo, int hi) {
if (lo > hi) return null;
int rootVal = preorder[preIdx++];
TreeNode root = new TreeNode(rootVal);
int mid = inMap.get(rootVal);
root.left = build(preorder, lo, mid - 1);
root.right = build(preorder, mid + 1, hi);
return root;
}
}
- Time Complexity: O(N)
- Space Complexity: O(N)