Construct Binary Tree from Preorder and Inorder Traversal
Problem
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).
Examples
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).
Constraints
- •
1 <= preorder.length <= 3000 - •
inorder.length == preorder.length - •
All values are unique
Hints
Hint 1
Preorder always visits the root first — preorder[0] tells you the root of the (sub)tree you're currently building.
Hint 2
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.
Hint 3
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).
Solutions
public TreeNode buildTreeBruteForce(int[] preorder, int[] inorder) {
return build(preorder, new int[]{0}, inorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] preIndex, int[] inorder, int inStart, int inEnd) {
if (inStart > inEnd) return null;
int rootVal = preorder[preIndex[0]++];
TreeNode root = new TreeNode(rootVal);
int mid = inStart;
while (inorder[mid] != rootVal) mid++; // LINEAR SCAN to find the root in inorder — the O(n^2) culprit
root.left = build(preorder, preIndex, inorder, inStart, mid - 1);
root.right = build(preorder, preIndex, inorder, mid + 1, inEnd);
return root;
}Time: O(n^2) worst case · Space: O(n)