题解 | 树查找

使用宽度优先遍历解决，每次将同层的所有结点加入到vec中，最终结果就是遍历以depth为下标的数组了，当每次从辅助队列中出队的结点是本层的第一个结点就要更新高度了（因为后面紧接着就要入队下一层的结点了），另外这里从1开始编号，可以很容易写出左孩子和右孩子编号

#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

// 输出某一深度的所有结点，当遍历到某一层时存入该层数组
int main() {
    int n, nodes[1001];
    queue<int> q;
    vector<int> vec[1000];
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &nodes[i]);
        }
        int depth;
        scanf("%d", &depth);

        // 广度优先遍历
        int num = 1; // 从1号结点开始入队
        q.push(num); // 辅助队列中入队的是下标，vec中入队的是元素
        int height = 1; // 只有一个结点的树高度为1
        for (int i = 0; i < 1000; i++) { // 处理连续输入
            vec[i].clear();
        }
        vec[height].push_back(nodes[num]); // 根结点存入高度为1的结点数组中
        int out, child1, child2; // 辅助队列出队结点的下标以及左右孩子下标
        while (!q.empty()) {
            out = q.front();
            // 如果出队的是本层最后一个结点，高度+1，在访问本层最后一个结点前已经要入队下一层结点，高度更新不及时
            // 改为出队本层第一个结点就更新高度
            if (out == pow(2, height - 1)) {
                ++height;
            }
            q.pop();
            child1 = 2 * out;
            child2 = 2 * out + 1;
            if (child1 <= n) {
                q.push(child1);
                vec[height].push_back(nodes[child1]);
            }
            if (child2 <= n) {
                q.push(child2);
                vec[height].push_back(nodes[child2]);
            }
        }
        // 输出某一层结点，若没有结点输出空
        if (!vec[depth].empty()) {
            for (unsigned int i = 0; i < vec[depth].size(); i++) {
                printf("%d ", vec[depth][i]);
            }
            printf("\n");
        }
        else {
            printf("EMPTY\n");
        }
    }
    return 0;
}