Reconstruct Binary Tree and Preorder Traversal

Given the inorder and postorder traversals of a binary tree, reconstruct the original binary tree and then output its preorder traversal.

The inorder traversal is given by \(I = [i_1, i_2, \dots, i_n]\), and the postorder traversal is given by \(P = [p_1, p_2, \dots, p_n]\). You can use the fact that the last element of the postorder sequence is the root of the tree. Let \(r = p_n\). Find the index of \(r\) in the inorder sequence; this splits \(I\) into the left subtree \(I_{left}\) and right subtree \(I_{right}\). Recursively, the same logic applies to both subtrees.

After reconstructing the binary tree, perform a preorder traversal (root, left, right) and output the result as a space-separated list of integers.

inputFormat

The input is read from standard input and consists of three lines:

1. The first line contains an integer \(n\), the number of nodes in the tree.
2. The second line contains \(n\) space-separated integers representing the inorder traversal.
3. The third line contains \(n\) space-separated integers representing the postorder traversal.

outputFormat

Print the preorder traversal of the reconstructed binary tree as space-separated integers on one line to standard output.

5
4 2 5 1 3
4 5 2 3 1

1 2 4 5 3