中序遍历 后序遍历求层序遍历
作者:
求你别WA了
,
2024-11-28 15:55:31
,
所有人可见
,
阅读 1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 30;
int a[N],b[N];
int p[N];
vector<int> depth[N];
void build(int al,int ar,int bl,int br,int d)
{
if(al > ar) return;
int root = a[ar];
depth[d].push_back(root);
int k = p[root];
//x-al = k-1-b1
build(al,k-1-bl+al,bl,k-1,d+1);
build(k-bl+al,ar-1,k+1,br,d+1);
}
int main()
{
int n;
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 u : depth[i])
cout << u << " ";
}
return 0;
}