FC树-L2-006 树的遍历
作者:
小花猪
,
2023-03-17 17:40:45
,
所有人可见
,
阅读 146
L2-006 树的遍历
#include <iostream>
#include <vector>
using namespace std;
const int N = 30+5;
int n,a[N],b[N],c[N];
vector<int> level[N];//存放每层的节点
void create(int al,int ar,int bl,int br,int d){
if(al>ar || bl>br) return;
int val = a[ar];
level[d].push_back(val);
int k = c[val];
create(al,k-bl-1+al,bl,k-1,d+1);//ar-al = k-bl-1 -> ar = k-bl-1-al
create(k-bl+al,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++) c[b[i]] = i;//c[i]表示后序遍历到的节点为i,在中序数组的位置
create(0,n-1,0,n-1,0);
for(int i=0; i<n; i++){
for(int x:level[i]){
cout<<x<<" ";
}
}
return 0;
}