Rebuild a Tree From Its Middle-Out and Node-Last Listings
Implement buildFromInPost
You are given two lists that describe the same binary tree with distinct values: inorder, which lists the left subtree, then the node, then the right subtree, and postorder, which lists the left subtree, then the right subtree, then the node itself. Rebuild the tree and return its root. (Two empty lists describe the empty tree.)
The last postorder value is the root, and its position in the inorder list splits the remaining values into the left and right subtrees. A map of inorder positions makes each split constant time; reading the postorder backwards, the right subtree has to be built before the left one.
Example 1:
Input: inorder = [3,6,9,14,17,20,25], postorder = [3,9,6,17,25,20,14]
Output: [14,6,20,3,9,17,25]
Example 2:
Input: inorder = [8,5], postorder = [8,5]
Output: [5,8]
Example 3:
Input: inorder = [], postorder = []
Output: []
+ 11 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all values are distinct, −1000 ≤ value ≤ 1000 - ●
inorder lists the node values as: left subtree, node, right subtree. postorder lists them as: left subtree, right subtree, then the node itself - ●
inorder and postorder 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
inorder =
postorder =