Construct Binary Tree from Preorder and Inorder Traversal
You are given two integer arrays: preorder, the sequence produced by visiting a binary tree root-first (node, then left subtree, then right subtree), and inorder, the sequence from visiting left subtree, then node, then right subtree. Both describe the same tree, and all values are distinct. Rebuild the tree and return its root.
The arrays have equal length, between 1 and 3,000. Distinct values matter: they let you locate any value's position in inorder unambiguously.
Examples
- Input:
- preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
- Output:
- [3,9,20,null,null,15,7]
3 is first in preorder, so it is the root. In inorder, [9] sits left of 3 (the left subtree) and [15,20,7] sits right (the right subtree). Recurse on each side.
- Input:
- preorder = [-1], inorder = [-1]
- Output:
- [-1]
- Input:
- preorder = [1,2], inorder = [2,1]
- Output:
- [1,2]
In inorder, 2 appears before the root 1, so 2 is a left child.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.