题目描述
给定一棵包含 n 个结点(编号 1∼n)的完全二叉树的层序遍历序列,请按照从左到右的顺序输出该树第 k 层的全部结点编号。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,表示该二叉树的层序遍历序列。
第三行包含整数 k。
输出格式
共一行,按照从左到右的顺序输出该树第 k 层的全部结点编号。
数与数之间用单个空格隔开。
若无该层结点,则输出 EMPTY。
数据范围
1≤n≤1000,
1≤k≤20
样例
输入样例:
4
1 2 3 4
2
输出样例:
2 3
算法1
(线性) $O(n)$
用数组按顺序存储 充分利用完全二叉树的性质
第 k 层结点的个数为 2^(k - 1)
前 k 层结点的个数为 2^k - 1
扩展:
第 i 个结点
其左子树 为第 2 * i 个结点
其右子树 为第 2 * i + 1 个结点
最不常用的性质 n0 = n2 + 1 (即叶子结点的个数等于度为 2 的结点个数加 1)
推导:
n0, n1, n2 分别代表度为 0,1, 2 结点的个数
二叉树中 结点个数 n = n0 + n1 + n2,
分支数可以表示成 n - 1 = n1 + 2 * n2
(共有 n - 1个分支, 分支数等于结点个数乘以各自的度数, 度为 1 的结点有 n1 * 1 个分支, 度为 2 的结点有 2 * n2 个分支)
联立两个关于 n 的等式 可以推出 n0 = n2 + 1
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m;
int a[N];
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i += 1)
cin >> a[i];
int k;
cin >> k;
if (1 << k - 1 > n) // 前 k 层第一个结点编号为 前 k - 1 层结点个数加 1, 2^(k - 1) - 1 + 1
cout << "EMPTY" << endl;
else
for (int i = 1 << k - 1; i <= (1 << k) - 1; i += 1)
{
if (a[i])
cout << a[i] << ' ';
else break;
}
return 0;
}