AcWing 1497. 树的遍历
原题链接
简单
作者:
尘轩
,
2024-04-17 12:33:42
,
所有人可见
,
阅读 2
c++代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 40;
int n;
int postorder[N], inorder[N];//存放后序遍历和中序遍历
//l[i]和r[i]分别存放的是结点i的左孩子和右孩子
//pos[i]存放的是结点i在中序遍历数组中的下标
unordered_map<int, int> l, r, pos;
//build函数的四个参数:
//il和ir表示当前子树的中序遍历的左端点和右端点在中序遍历数组中的下标
//pl和pr表示当前子树的后序遍历的左端点和右端点在后序遍历数组中的下标
//build函数返回的是当前子树的根节点
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, pl + k - il - 1);
//当前子树的根节点有右子树,就更新当前子树根节点的右孩子(根节点右子树的根节点,递归处理)
if (ir > k) r[root] = build(k + 1, ir, pl + k - il, pr - 1);
return root;
}
//层序遍历
void bfs(int root) {
queue<int> q;
q.push(root);
while (!q.empty()) {
auto t = q.front();
q.pop();
if (l[t]) q.push(l[t]);
if (r[t]) q.push(r[t]);
cout << t << " ";
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> postorder[i];
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;
}