可以根据后序的最后一个点把中序划分为左右俩子树,中序划分的左右俩子树在后序遍历序列里又可以分为两段,如是递归即可
方法1:dfs
#include<iostream>
#include<vector>
using namespace std;
const int N = 40;
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){
if(al > ar) return;
int root = a[ar]; //每层根节点等于后序遍历的末尾
level[d].push_back(root);
int k = p[root]; //得到中序的位置,方便求后序的首、尾
build(al, al + k - bl - 1, 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(auto x : level[i]){
cout << x << ' ';
}
}
return 0;
}
方法2:bfs
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 40;
int n;
int a[N], b[N]; //中序 后序
unordered_map<int, int> l, r, pos;
queue<int> q;
int build(int al, int ar, int bl, int br){ //中 + 后
int root = b[br]; //根等于后序遍历的最后一个
int k = pos[root];
if(al < k) l[root] = build(al, k - 1, bl, bl + k - al - 1);
if(k < ar) r[root] = build(k + 1, ar, bl + k - al, br - 1);
return root; //返回的是根节点
}
void bfs(int root){
q.push(root);
while(q.size()){
auto t = q.front();
q.pop();
cout << t << ' ';
if(l.count(t)) q.push(l[t]);
if(r.count(t)) q.push(r[t]);
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> b[i]; // 后序
for(int i = 0; i < n; i ++) cin >> a[i]; // 中序
for(int i = 0; i < n; i ++) pos[a[i]] = i;
int root = build(0, n - 1, 0, n - 1);
bfs(root);
return 0;
}