Description
Today when you stepped out of your house, you saw something fall from the sky and land at the park near your house. You felt worried and curious, so you ran quickly toward the park to check it out. Fortunately, the falling thing isn’t a plane, a bomb, or something harmful, and it is just a binary tree breaking into pieces. Additionally, there was a paper by its side. You picked up the paper and realized that it is the information of the binary tree. Since the binary tree's live matters, you collect the breaking pieces of the binary tree to your house and decide to reconstruct it.
So here’s the problem.
You will get some information about a binary tree:
- The inorder sequence.
- (n-1)/2 pairs of nodes, in which the nodes in the same pair have the same parent.
Please print the preorder of the reconstructed binary tree.
It is guaranteed that the tree exists and is unique, and each node would either have no child or 2 children. Note that there's no fixed order for the pairs, and the first node of a pair is not necessarily the left child.
Hint:
- You can use the following algorithm.
- Let the root node be the one that does not appear in any child pair.
- Starting from the root, find the child pair in which one node is to the left and one node is to the right of the root in the inorder sequence, and repeat the process recursively.
- Consider the following example.
Input
The first line contains an integer n, which means there are n nodes in the binary tree.
The second line contains n integers, representing the inorder sequence.
Each of the following (n - 1)/2 lines contains two integers, which means the two nodes have the same parent.
Constraints:
n % 2 == 1
Cases 1~7: n < 10
Cases 8~11: n < 3000
The inorder sequence contains n distinct numbers. For each number x, 1 ≤ x ≤ n.
Output
A line that represents the preorder sequence.
Please print ‘\n’ at the end.