后序遍历+中序遍历 推原树
作者:
无苦邪
,
2024-04-16 12:29:28
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int n;
//后序 中序 记录中序遍历每个数的所在位置
int a[N],b[N],p[N];
vector<int> level[N];
// al,ar 后序遍历某个子树的范围
// bl,br 中序遍历某个子树的范围
void build(int al,int ar,int bl,int br,int d) {
// 后序遍历 左节点在右节点 右边退出
if(al > ar) return;
// 后序遍历 最后一个元素就是根节点
int val = a[ar];
level[d].push_back(val);
int k = p[val];
//k -bl - 1
// 1 2 3
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];
p[b[i]] = i;
}
build(0,n - 1,0,n - 1,0);
// 层次遍历
for(int i = 0; i < n ; i ++) {
for(int x : level[i]) {
if(!i) {
cout << x;
} else {
cout << ' ' << x;
}
}
}
return 0;
}