#include<bits/stdc++.h>
using namespace std;
const int N=50;
int n;//定义节点的数量
int in[N],post[N];//in表示中序遍历,post表示后续遍历
int l[N],r[N];//每一个节点的左右子节点
map<int,int>mp;
int level[N];//层序遍历
int nlevel[N];//存每一个节点的层次
void build(int il,int ir,int pl,int pr)//后序+中序建树
{
int root=post[pr];//对于后续遍历,它的根节点在最右边
int k=mp[root];//找到跟节点在中序遍历中的位置
int numlen=k-il;//获得左子树的长度
if(k>il)//表示当前的左子树还存在
build(il,k-1,pl,pl+numlen-1);
if(k<ir)//表示当前的右子树还存在
build(k+1,ir,pl+numlen,pr-1);
if(k>=ir)//表示这棵树的右子节点已经不存在了
r[root]=-1;
else
r[root]=post[pr-1];
if(k<=il)//表示这棵树的左子节点已经不存在了,那么就要把左子节点设置为-1
l[root]=-1;
else
l[root]=post[pl+numlen-1];
}
void bfs(int root)
{
int tt=0,hh=0;
level[++tt]=root;//将根节点存进来
nlevel[root]=1;//初始根节点的层次为1
while(tt>hh)
{
int para=level[++hh];
if(l[para]!=-1)//如果存在左子节点
{
level[++tt]=l[para];
nlevel[tt]=nlevel[hh]+1;
}
if(r[para]!=-1)//如果存在右子节点
{
level[++tt]=r[para];
nlevel[tt]=nlevel[hh]+1;
}
}
}
int main()
{
memset(nlevel,-1,sizeof nlevel);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&in[i]);//输入中序遍历序列
mp[in[i]]=i;//将每一个点和下标建立一一映射,便于后续寻找
}
for(int i=1;i<=n;i++)scanf("%d",&post[i]);//输入后续遍历序列
build(1,n,1,n);
bfs(post[n]);
printf("%d",level[1]);
int ld=2;//区间的左端点
int rd=2;//需要进行翻转的区间的右端点
bool flag=true;//记录是否需要翻转
int cnt=1;//记录当前遍历的点数,遍历完就退出
while(cnt<n)
{
while(nlevel[rd]==nlevel[ld]&&rd<=n)//如果当前的节点所在层次和ld相同
rd++;
rd--;//上一步退出循环说明已经遍历到不是这一层了,那么就要退回一步
if(flag==true)//表示当前是偶数,那么就是从左往右进行输出,不需要进行反转
{
for(int k=ld;k<=rd;k++)
{
printf(" %d",level[k]);
cnt++;
}
flag=false;//表示下一层是要从右往左进行遍历的
}
else
{
for(int k=rd;k>=ld;k--)
{
printf(" %d",level[k]);
cnt++;
}
flag=true;//表示下一层是要从左往右进行遍历的
}
ld=rd+1;//遍历到下一个区间
rd=ld;
}
return 0;
}
666%%%