在 NOI 系列竞赛（如 NOIP、CSP-S）中，处理树形结构题目时，代码的稳定性和运行效率至关重要。

由于这道题本身的时间复杂度下限就是 $O(N)$（每个节点必须访问一次），我们优化的重点在于减少内存分配开销、防止递归栈溢出以及提升代码在底层评测机上的执行速度。

以下是三个版本的代码，从简单的递归逻辑到竞赛级别的数组优化版本。

版本一：递归深度优先搜索 (DFS) 模拟层序

思路：虽然是层序遍历，但我们可以通过 DFS 记录当前节点的“深度”。通过深度作为索引，将节点值填入对应的 vector 中。 优点：代码极其简洁，适合在比赛时间紧迫时快速实现。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];
vector<vector<int>> res;

// u: 当前节点编号, d: 当前深度 (从0开始)
void dfs(int u, int d) {
    if (u == -1) return;

    // 如果当前深度超过了 res 的现有大小，说明进入了新的一层
    if (d >= res.size()) {
        res.push_back(vector<int>());
    }

    res[d].push_back(val[u]); // 将当前节点值加入对应深度的 vector
    dfs(l_son[u], d + 1);      // 递归左子树，深度+1
    dfs(r_son[u], d + 1);      // 递归右子树，深度+1
}

int main() {
    int n;
    if (!(cin >> n) || n == 0) return 0;

    // NOI 风格输入：节点关系存储
    for (int i = 0; i < n; i++) {
        cin >> l_son[i] >> r_son[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> val[i];
    }

    dfs(0, 0); // 从根节点（编号0）开始 DFS

    // 输出结果
    for (const auto& level : res) {
        for (int i = 0; i < level.size(); i++) {
            cout << level[i] << (i == level.size() - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

复杂度分析：

• 时间：$O(N)$，每个节点访问一次。
• 空间：$O(H)$，$H$ 为树的高度。最坏情况下（链状树）空间复杂度为 $O(N)$，可能会触发栈溢出（但在 $N=2000$ 时安全）。

版本二：标准 STL 广度优先搜索 (BFS)

思路：使用 std::queue。为了分层，在处理每一层之前先记录当前队列的大小 sz。 优点：逻辑最符合“层序遍历”的本质，由于没有递归，完全不用担心栈溢出。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n) || n == 0) return 0;

    for (int i = 0; i < n; i++) cin >> l_son[i] >> r_son[i];
    for (int i = 0; i < n; i++) cin >> val[i];

    queue<int> q;
    q.push(0); // 假设 0 是根节点

    while (!q.empty()) {
        int sz = q.size(); // 关键点：当前队列里的节点全属于同一层
        vector<int> current_level;

        while (sz--) {
            int u = q.front();
            q.pop();
            current_level.push_back(val[u]);

            // 易错点：入队前必须判断子节点是否存在（本题用 -1 表示不存在）
            if (l_son[u] != -1) q.push(l_son[u]);
            if (r_son[u] != -1) q.push(r_son[u]);
        }

        // 输出当前层
        for (int i = 0; i < current_level.size(); i++) {
            cout << current_level[i] << (i == current_level.size() - 1 ? "" : " ");
        }
        cout << "\n"; // 使用 \n 替代 endl，在大数据量下更快
    }

    return 0;
}

复杂度分析：

• 时间：$O(N)$。
• 空间：$O(W)$，$W$ 为树的最大宽度。

版本三：竞赛级优化（数组模拟队列与预分配空间）

思路：在 NOI 提高组中，如果 $N$ 达到 $10^6$，std::vector 的频繁扩容和 std::queue 的动态分配会变慢。我们使用静态数组模拟队列，并直接根据每一层的节点数进行处理。

#include <cstdio> // 使用 fast I/O 或 scanf

const int MAXN = 2005;
int val[MAXN], l_son[MAXN], r_son[MAXN];
int q[MAXN]; // 静态数组模拟队列，极其高效

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;

    for (int i = 0; i < n; i++) scanf("%d %d", &l_son[i], &r_son[i]);
    for (int i = 0; i < n; i++) scanf("%d", &val[i]);

    int head = 0, tail = 0;
    q[tail++] = 0; // 根入队

    while (head < tail) {
        int sz = tail - head; // 当前层的节点数量
        
        // 技巧：在这一步，q[head] 到 q[tail-1] 存储的就是当前层所有节点编号
        for (int i = 0; i < sz; i++) {
            int u = q[head + i];
            printf("%d%c", val[u], (i == sz - 1 ? '\n' : ' '));
        }

        // 将下一层节点加入队尾，注意不要修改当前的 head
        int next_level_count = 0;
        for (int i = 0; i < sz; i++) {
            int u = q[head++]; // 真正弹出当前层
            if (l_son[u] != -1) q[tail++] = l_son[u];
            if (r_son[u] != -1) q[tail++] = r_son[u];
        }
    }

    return 0;
}

总结与优化建议

1. 时间复杂度分析思考过程

• 访问控制：无论 BFS 还是 DFS，树的结构保证了没有环，因此不需要 vis[] 数组。每个节点进出队列各一次，时间复杂度严格 $O(N)$。
• 优化方向：在 $N$ 很大时，std::endl 会刷新缓冲区导致速度变慢，务必使用 \n。std::vector 的 push_back 具有均摊 $O(1)$ 的复杂度，但在竞赛中，如果能预估大小，使用 vector::reserve() 可以减少 30% 以上的耗时。

2. 空间复杂度优化建议

• 内存池：在处理大规模树结构时，尽量避开 new 关键字申请内存，改用数组下标模拟指针，这能有效避免内存碎片的产生。
• 复用空间：如果只需要输出而不需要保存所有结果，可以像版本三那样，在输出当前层后立即释放或覆盖，将空间复杂度压制在 $O(W)$（树的最大宽度）。

3. 易错点总结

• 空树处理：$n=0$ 时如果不特判，q.front() 或 val[0] 可能会导致越界。
• 队列长度更新：在 BFS 循环内部，q.size() 是动态变化的。必须在处理每层前先用一个变量 sz 固定住当前层的节点数，否则会把刚入队的下一层节点也一起处理了。
• 节点编号：注意题目中节点编号是从 0 开始还是从 1 开始。如果是从 1 开始，数组大小要开 MAXN + 1。

4. 关键词识别

• “按层” $\rightarrow$ 锁定 BFS。
• “从左到右” $\rightarrow$ 确定子节点入队顺序：q.push(left); q.push(right);。
• “每一层”作为一个整体输出 $\rightarrow$ 确定需要使用 sz = q.size() 逻辑进行分层控制。