Reconstruct Binary Tree and Postorder Traversal

Given two sequences representing the preorder and inorder traversals of a binary tree, reconstruct the binary tree and output its postorder traversal.

The binary tree can be uniquely constructed since all node values are distinct. Recall the traversal orders:

• Preorder: \(root \rightarrow left \rightarrow right\)
• Inorder: \(left \rightarrow root \rightarrow right\)
• Postorder: \(left \rightarrow right \rightarrow root\)

inputFormat

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

outputFormat

Output a single line containing \(n\) space-separated integers representing the postorder traversal of the reconstructed binary tree.

6
1 2 4 5 3 6
4 2 5 1 6 3

4 5 2 6 3 1