Rebuild a Tree From Its Node-First and Middle-Out Listings
Implement buildFromPreIn
You are given two lists that describe the same binary tree with distinct values: preorder, which lists each node before its left subtree and its right subtree, and inorder, which lists the left subtree, then the node, then the right subtree. Rebuild the tree and return its root. (Two empty lists describe the empty tree.)
The first preorder value is the root, and its position in the inorder list splits the remaining values into the left and right subtrees. Doing that split with a scan at every node is slow; storing the inorder positions in a map and reading the preorder with a running index makes each step constant time.
Example 1:
Input: preorder = [9,4,2,6,15,11,18], inorder = [2,4,6,9,11,15,18]
Output: [9,4,15,2,6,11,18]
Example 2:
Input: preorder = [5,8], inorder = [8,5]
Output: [5,8]
Example 3:
Input: preorder = [], inorder = []
Output: []
+ 11 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all values are distinct, −1000 ≤ value ≤ 1000 - ●
preorder lists the node values as: node, then its whole left subtree, then its whole right subtree. inorder lists them as: left subtree, node, right subtree - ●
preorder and inorder have the same length and describe the same tree (this is guaranteed) - ●
Return the root of the tree they describe. The result is checked as a level-order list (missing children shown as null); two empty listings give the empty tree
preorder =
inorder =