Reconstruct Binary Tree

Reconstruct Binary Tree
Recursion

Given the pre-order traversal and in-order traversal of a binary tree, output the post-order traversal of the binary tree.

Input format:
line 1: number of nodes
line 2: the pre-order traversal;
line 3: the in-order traversal.
note: The tree nodes are labeled 1, 2, ..., n

Example 1

Input:
9
1 2 3 4 5 6 7 8 9
3 2 5 4 6 1 8 7 9
Output:
3 5 6 4 2 8 9 7 1
Explanation:
The tree can be reconstructed from the input as: