题目描述
给定一棵包含 n 个结点(编号 1∼n)的完全二叉树的层序遍历序列,请按照从左到右的顺序输出该树第 k 层的全部结点编号。
样例
输入样例:
4
1 2 3 4
2
输出样例:
2 3
``````
思路:已知树为完全二叉树,所以可以直接用数组来存储该树,设下标为1储存的是根节点的值,设left为本层最左边的元素下标,设right为本层最右边的元素下标,根据递推公式可以得到,下一层元素所处区间为[left * 2,right * 2 + 1],对left和right不断更新,直到第k层
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int k;
int tree[N];
int main(){
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++)
cin >> tree[i];
cin >> k;
int left = 1,right = 1; //初始化第一层的left,right
for(int i = 2 ; i <= k ; i ++){
left = left * 2;
right = right * 2 + 1;
}
//判断条件,如果left大于n的话说明k层没有元素
if(left > n){
cout << "EMPTY";
return 0;
}
//确定右边界
right = min(right,n);
for(int i = left ; i <= right ; i ++)
cout << tree[i] <<' ';
}