9240 - 二叉树的后序遍历

二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,如下图所示:

二叉树的遍历方法有很多种,常用的有以下四种:

先序遍历:先访问根节点,再访问左子树,最后访问右子树。先序遍历的结果为:1 2 4 5 3。

中序遍历:先访问左子树,再访问根节点,然后访问右子树。中序遍历的结果为:4 2 5 1 3。

后序遍历:先访问左子树,再访问右子树,最后访问根节点。后序遍历的结果为:4 5 2 3 1。

层次遍历:按层次从小到大逐个访问,同一层次按照从左到右的次序。层次遍历的结果为1 2 3 4 5。

现在给出一棵有n个结点的二叉树的先序遍历和中序遍历,试求出这棵二叉树的后序遍历结果。

输入

第一行输入一个正整数n,表示二叉树有n个节点。

第二行有n个正整数,中间用空格隔开,表示先序遍历的结果。

第三行有n个正整数,中间用空格隔开,表示中序遍历的结果。

输出

输出一行含n个正整数,中间用空格隔开,表示后序遍历的结果。

样例

输入

5
1 2 4 5 3
4 2 5 1 3

输出

4 5 2 3 1

输入

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

输出

7 4 5 2 6 3 1
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题