AcWing/天梯赛
1497. 树的遍历/L2-006 树的遍历
使用vector<int> c[N]存每一层的节点。build()函数递归建树，并保存当前根节点层数。a[]为树的后序遍历数组，b[]为树的中序遍历数组，p[]存的是树的后序遍历数组元素值的位置。
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int a[N], b[N], p[N];
vector<int> c[N];
void build(int al, int ar, int bl, int br, int dep){
if(al > ar) return;
int val = a[ar];
c[dep].push_back(val);
int k = p[val];
build(al, k - 1 - bl + al, bl, k - 1, dep + 1);
build(k - bl + al, ar - 1, k + 1, br, dep + 1);
}
int main(){
int n;
cin >> n;
for(int i = 0; i <= n - 1; i++) cin >> a[i];
for(int i = 0; i <= n - 1; i++) cin >> b[i];
for(int i = 0; i <= n - 1; i++) p[b[i]] = i;
build(0, n - 1, 0, n - 1, 0);
for(int i = 0; i <= N - 1; i++) for(int j : c[i]) cout << j << ' ';
cout << endl;
return 0;
}