build建树过程中的区间处理问题
C++代码
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 40;
int n;
// 后序 中序
int postorder[N], inorder[N];
// 使用哈希表 存储每一个结点的左右子节点 二叉树 有(左/右)子节点的话只会有一个
unordered_map<int, int> l, r;
// 存 后序遍历中的根节点rootroot(当前的) 在中序遍历下的下标k
// 下标k把中序遍历序列划分为了两个区间
unordered_map<int, int> pos;
int q[N]; // bfs 手动模拟的好处就是可以记录下所有的结点 因为改变的只是下标
// 中序左端点 中序右端点 后序左端点 后序右端点
// 返回值是当前的根节点 因为我们要从根结点开始bfs
int build(int il, int ir, int pl, int pr){
int root = postorder[pr];
int k = pos[root];
// 建树的过程
// 左子树存在 则找到左孩子(即下一层递归的根)
if(il < k){
l[root] = build(il, k-1, pl, k-1-il+pl);
}
if(ir > k){
r[root] = build(k+1, ir, k-il+pl, pr-1);
}
return root;
}
// 层序遍历 从根开始bfs即可
void bfs(int root){
int hh = 0, tt = 0;
q[0] = root;
while(hh <= tt){
int t = q[hh++];
// 若存在左/右子树 则加入队列
if(l.count(t)) q[++tt] = l[t];
if(r.count(t)) q[++tt] = r[t];
}
cout << q[0];
for(int i = 1; i < n; i++){
cout << " " << q[i];
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> postorder[i];
// 建立 中序遍历结点和下标的映射关系 方便之后找k
for(int i = 0; i < n; i++){
cin >> inorder[i];
pos[inorder[i]] = i;
}
int root = build(0, n-1, 0, n-1);
bfs(root);
return 0;
}