hardTreesPure DSA~35 min
Reconstruct a Tree From Preorder and Inorder Logs
Two traversal logs of a binary tree survived — a preorder log and an inorder log. Rebuild the exact tree structure they came from.
Problem
Given two integer arrays preorder and inorder representing the preorder and inorder traversals of a binary tree with unique values, construct and return the binary tree.
Input
Two arrays preorder and inorder of the same length.
Output
The root of the reconstructed binary tree.
Constraints
- 1 <= preorder.length <= 3000
- inorder is a permutation of preorder.
- All 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]
3 is the root; 9 is its left subtree; 20 with children 15,7 is its right.
Example 2
Input
preorder = [-1], inorder = [-1]
Output
[-1]
A single-node tree.