链接: https://cses.fi/problemset/task/1702

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

遍历二叉树节点有三种常见方式：

• 前序：先处理根，再处理左子树，最后处理右子树。
• 中序：先处理左子树，再处理根，最后处理右子树。
• 后序：先处理左子树，再处理右子树，最后处理根。

有一棵含有 $n$ 个节点、标号互不相同的二叉树。给定这棵树的前序遍历和中序遍历，你的任务是求出它的后序遍历。

输入

第一行包含一个整数 $n$：节点数量。节点编号为 $1,2,\dots,n$。

接下来有两行分别描述树的前序遍历和中序遍历。两行均由 $n$ 个整数组成。

你可以假定输入对应一棵合法的二叉树。

输出

输出这棵树的后序遍历。

数据范围

$1 \le n \le 10^5$

样例输入

5
5 3 2 1 4
3 5 1 2 4

样例输出

3 1 4 2 5