题目描述
给定一棵包含 n 个结点(编号 1∼n)的完全二叉树的层序遍历序列,请按照从左到右的顺序输出该树第 k 层的全部结点编号。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,表示该二叉树的层序遍历序列。
第三行包含整数 k。
输出格式
共一行,按照从左到右的顺序输出该树第 k 层的全部结点编号。
数与数之间用单个空格隔开。
若无该层结点,则输出 EMPTY。
数据范围
1≤n≤1000,
1≤k≤20
样例
输入样例:
4
1 2 3 4
2
输出样例:
2 3
思路:这道题需要用到二叉树的性质,满二叉树每一层有多少节点,公式是2的k-1次幂,k就是为每层层数,层数从1开始计算。因为题中问的是输出每一层的节点元素。所以这里还需要计算出每一层的第一个节点下标,这个下标我们可以记为start,end也就可以求出了,用start+每一层的节点数。我们这个树就可以转化成一个从0开始的数组。
C++ 代码
#include<iostream>
using namespace std;
#include<cmath>
const int N=101000;
int a[N];
int main(){
int m;
cin>>m;
for(int i=0;i<m;i++) //先把节点读入数组
cin>>a[i];
int n;
cin>>n;
int start=pow(2,n-1)-1; //计算每一层的最初节点
int end=start+pow(2,n-1); //先当成满二叉树计算终止节点
int res=0;
if(start>m-1) //进行特判,防止越界
puts("EMPTY");
else
for(int i=start;i<end;i++){
if(a[i]){ //因为我们刚开始把这个想象成了满二叉树,但是题中问的是完全二叉树
cout<<a[i]<<' '; //因为所有数的节点都是不为0的数,所以当a[i]不为0时,在进行输出
}
}
return 0;
}
如果完全二叉树和满二叉树的关系还不清楚的话可以去查阅一下资料,另附一张本人手绘的图片供大家参考(字丑勿喷哈哈哈哈)
刚开始试着发一些题解,希望大家多多指教。