题目描述
笛卡尔树 是由一系列不同数字构成的二叉树。
树满足堆的性质,中序遍历返回原始序列。
最小笛卡尔树表示满足小根堆性质的笛卡尔树。
例如,给定序列 $\{8, 15, 3, 4, 1, 5, 12, 10, 18, 6\}$,则生成的最小堆笛卡尔树如图所示。
现在,给定一个长度为 $N$ 的原始序列,请你生成最小堆笛卡尔树,并输出其层序遍历序列。
输入格式
第一行包含整数 $N$。
第二行包含 $N$ 个两两不同的整数,表示原始序列。
输出格式
共一行,输出最小堆笛卡尔树的层序遍历序列。
数据范围
$1 \le N \le 30$,
原始序列中元素的取值范围 $[−2147483648, 2147483647]$。
输入样例:
10
8 15 3 4 1 5 12 10 18 6
输出样例:
1 3 5 8 4 6 15 10 12 18
解题思路
首先,这棵树得满足小根堆的性质,即父节点大于子节点。因此根节点只能是序列中最小的那个数。
又因为树的中序遍历序列为原序列,所以最小数的左边全在它的左子树内,右边同理。
综上,我们可以想到一个递归策略:每次遍历一段区间找出它的最小值即父节点,再按照最小数的位置把这段区间分成左右两个子区间即两颗子树,递归处理。
由于题目要求层序遍历序列,我们把递归的 dfs
序改成 bfs
序就好了。
AC 代码
#include <iostream>
#include <queue>
#define N 35
#define inf 1u<<31
using namespace std;
struct node {int l, r;};
int n, a[N];
queue <node> q;
void solve (int l, int r) // 解决一段子区间
{
if (l > r)
{
return ;
}
long long mn = inf, pos;
for (int i = l; i <= r; i ++)
{
if (a[i] < mn)
{
pos = i, mn = a[i];
}
}
cout << mn << " ", q.push ({l, pos - 1}), q.push ({pos + 1, r});
return ;
}
int main ()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
q.push ({1, n});
while (!q.empty ())
{
solve (q.front ().l, q.front ().r), q.pop (); // bfs
}
return 0;
}
感谢观看!
$$\href {/blog/content/19548/} {\color {MediumSlateBlue} {【暑假每日一题】题解}}$$
诈尸