AcWing 1589. 根据层序遍历构建二叉搜索树
原题链接
中等
作者:
jokerlove
,
2022-07-06 18:21:01
,
所有人可见
,
阅读 229
/*
利用二叉搜索树的中序遍历为有序序列的规则
先dfs建树,再bfs层序遍历
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;
int v[N], l[N], r[N];
int a[N], q[N];
int idx = 0;
void dfs(int u) // 节点下标u
{
if (u == -1)
return;
dfs(l[u]);
v[u] = a[idx++]; // 中序遍历赋值
dfs(r[u]);
}
void bfs()
{
int head = 0, tail = 0;
q[0] = 0; // 入队
while (head <= tail)
{
int tmp = q[head++]; // 取出头结点+出队
cout << v[tmp] << ' ';
if (l[tmp] != -1)
q[++tail] = l[tmp];
if (r[tmp] != -1)
q[++tail] = r[tmp]; // 将左右孩子入队
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> l[i] >> r[i]; // 记录左右孩子节点下标
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
dfs(0); // 传入根节点
bfs();
return 0;
}