9240 - 二叉树的后序遍历
时间限制 : 1 秒
内存限制 : 512 MB
二叉树是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