Given two integer arrays preorder and inorder representing the preorder and inorder traversal of a binary tree, construct and return the binary tree (values are unique).
Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Explanation: Root is 3 (preorder[0]); inorder splits into [9] (left subtree) and [15,20,7] (right subtree).
1 <= preorder.length <= 3000inorder.length == preorder.lengthAll values are uniquePreorder always visits the root first — preorder[0] tells you the root of the (sub)tree you're currently building.
Once you know the root's value, find it in the inorder array: everything to its left in inorder is the left subtree, everything to its right is the right subtree.
A hash map from value to its inorder index turns 'find the root in inorder' from an O(n) scan into an O(1) lookup — critical for staying out of O(n^2).
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inorderIndex = new HashMap<>();
for (int i = 0; i < inorder.length; i++) inorderIndex.put(inorder[i], i);
return build(preorder, new int[]{0}, 0, inorder.length - 1, inorderIndex);
}
private TreeNode build(int[] preorder, int[] preIndex, int inStart, int inEnd, Map<Integer, Integer> inorderIndex) {
if (inStart > inEnd) return null;
int rootVal = preorder[preIndex[0]++]; // preorder cursor advances exactly once per node, across the whole recursion
TreeNode root = new TreeNode(rootVal);
int mid = inorderIndex.get(rootVal);
root.left = build(preorder, preIndex, inStart, mid - 1, inorderIndex); // build left BEFORE right — matches preorder's own left-first order
root.right = build(preorder, preIndex, mid + 1, inEnd, inorderIndex);
return root;
}Time: O(n) · Space: O(n)