Skip to main content

3537.树查找

caution

原题链接：https://www.acwing.com/problem/content/3540/

思路​

看题貌似涉及到树，但其实很简单。（题目越复杂思路越简单）

因为题目给出是完全二叉树，所以对应树的层序遍历一定是连续的。只需要找到当 kk 和层数和开始遍历的下标之间的关系。

不难发现，开始遍历的第一个元素的下标和层数的关系是 2k−12^{k-1}，也就是说，start_index=2k−1\text{start\_index}=2^{k-1}。

因为完全二叉树每一层最多的节点个数为 2m−12^{m-1}，此处 mm 为层数并且根节点为第 11 层，所以只需要从 start_index\text{start\_index} 开始，遍历后 2k−12^{k-1} 个元素即可。（加上判断层是否为空和边界判断即可实现）

  • 判空：当开始下标的值比总数要少时，此层为空
  • 边界判断：遍历的下标小于总数 nn

代码​

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, k;
int a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> k;

    int st = pow(2, k - 1);
    if (n < st)
        cout << "EMPTY";
    else
        for (int i = 1; i <= pow(2, k - 1) && st + i - 1 <= n; i++) {
            cout << a[st + i - 1] << " ";
        }

    return 0;
}