Binary Tree Traversals¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
On the target judge, multiply the reference program's largest per-case median time by \(2\) and round up to a multiple of \(0.5\) seconds. See environment and measurements.
Story¶
An archivist has recorded the preorder and inorder traversals of a binary tree. Recover the missing postorder traversal.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
You are given the preorder and inorder traversals of the same rooted binary tree. It has \(n\) nodes labeled from \(1\) to \(n\) , each used exactly once. Left and right subtrees are distinguished, and either may be empty.
- Preorder: root, left subtree, right subtree.
- Inorder: left subtree, root, right subtree.
- Postorder: left subtree, right subtree, root.
Find its postorder traversal.
Input Format¶
The first line contains \(n\) . The second line contains the preorder traversal, and the third line contains the inorder traversal, each consisting of \(n\) integers.
Output Format¶
Print the postorder traversal as \(n\) space-separated integers on one line.
Examples¶
Example 1¶
Input¶
8
3 1 4 5 6 2 7 8
5 4 1 6 3 2 7 8
Output¶
5 4 6 1 8 7 2 3
Example 2¶
Input¶
4
1 2 3 4
4 3 2 1
Output¶
4 3 2 1
Example 3¶
Input¶
3
2 1 3
1 2 3
Output¶
1 3 2
Example Explanation¶
In the third example, the root is \(2\) , with left child \(1\) and right child \(3\) , so the postorder is \(1,3,2\) . The second example is a chain of left children.
The labels pre , in and post denote preorder, inorder and postorder. Left and right children are drawn on their corresponding sides.
Constraints and Guarantees¶
All inputs satisfy: \(1\le n\le10^6\) . Both traversals are permutations of \(1\) through \(n\) and are guaranteed to describe the same binary tree.
| Score | Additional conditions |
|---|---|
| 100% | None |