Description
Elfnt is hungry and wants to order a delicious tree for breakfast.
Since it’s breakfast, the waiter needs the tree’s pre-order as the meal code.
However, elfnt has forgotten the pre-order.
Fortunately, he still remembers the tree’s in-order and post-order.
Please help elfnt reconstruct the pre-order so he can enjoy his breakfast.
Hint: Try to use the given information to find the size of left and right subtree. Then do the recursion to find the answer.
Input
- The first line contains $n$ integers -- the in-order of the tree.
- The second line contains $n$ integers -- the post-order of the tree.
Constraints
- $1 \le n \le 1000$
- The tree contains n distinct nodes, labeled $1$ to $n$.
- The input is guaranteed to describe a valid binary tree.
Output
Print the pre-order of the tree, each number followed by a space (including the last one).
No \n at the end.