树的遍历
作者:
đł_0
,
2024-04-25 13:56:58
,
所有人可见
,
阅读 6
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n;
int a[N],b[N],p[N];
vector<int> level[N];
void build(int al,int ar,int bl,int br,int d){ //d的作用是记录树的深度,然后后面level[]数组来存,方便层序遍历
if(al>ar) return ;
int val=a[ar];//后序遍历最后一个为树的头结点
level[d].push_back(val);
int k=p[val];
build(al,al+k-1-bl,bl,k-1,d+1);
build(al+k-bl,ar-1,k+1,br,d+1);
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) p[b[i]]=i;//记录中序序列每个值的位置下标
build(0,n-1,0,n-1,0);
for(int i=0 ;i<n;i++)
for(int x:level[i])
cout<<x<<' ';
return 0;
}