#K79592. Binary Tree Reconstruction and Postorder Traversal

    ID: 35342 Type: Default 1000ms 256MiB

Binary Tree Reconstruction and Postorder Traversal

Binary Tree Reconstruction and Postorder Traversal

You are given the preorder and inorder traversal sequences of a binary tree. Your task is to reconstruct the binary tree and then output the postorder traversal sequence of the tree.

The binary tree is defined as follows:

\( TreeNode = \{ value, left, right \} \), where each node may have a left subtree and a right subtree. It is guaranteed that the given traversals represent a valid binary tree.

Example:

Input:
6
1 2 4 5 3 6
4 2 5 1 6 3

Output: 4 5 2 6 3 1

</p>

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the binary tree.

The second line contains \(n\) space-separated integers, which is the preorder traversal of the tree.

The third line contains \(n\) space-separated integers, which is the inorder traversal of the tree.

outputFormat

Print a single line containing the postorder traversal of the binary tree. The values should be separated by a single space.

## sample
6
1 2 4 5 3 6
4 2 5 1 6 3
4 5 2 6 3 1