Loading...
Loading...
Loading...
A knockout tournament bracket was saved as two lists before the laptop crashed. The preorder list writes a node, then its whole left part, then its whole right part. The inorder list writes the left part, then the node, then the right part. All values are different.
Rebuild the tree from the two lists. Print its postorder list: the left part, then the right part, then the node.
Example 1
Input
5 3 9 20 15 7 9 3 15 20 7
Output
9 15 7 20 3
The root is 3, the first in preorder. In inorder, 9 is left of 3 and 15 20 7 are right of it. So the postorder is 9 15 7 20 3.
Example 2
Input
3 1 2 3 3 2 1
Output
3 2 1
Each node is left of the one before it in inorder, so this is a left chain: 3 → 2 → 1 in postorder.
Try the problem first. Open one hint at a time.
The first value in preorder is the root.
Find the root in the inorder list. Everything to its left forms the left part, everything to its right forms the right part.
The left part has k values in inorder, so the next k values in preorder belong to it, and the rest to the right part.
Store each value's inorder position in a HashMap, so finding the root takes O(1) time instead of a scan.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor