二叉树层次遍历（Level-order Traversal）

算法原理

层次遍历（层序遍历）按层走：先访问根（第 0 层），再从左到右访问第 1 层，然后第 2 层……它是二叉树上唯一不沿深度优先走的 mainstream 遍历——本质就是树上的广度优先搜索（BFS），引擎是一个先进先出（FIFO）的队列：出队一个节点就记录它，同时把它的孩子（先左后右）从队尾入队。

本动画用同一棵 7 节点的完全二叉搜索树演示（默认 2s/拍，全片 9 拍）：

树：根 5（左子 3，右子 8）；3 的孩子 1、4；8 的孩子 7、9
层次输出：5 3 8 1 4 7 9
节拍：宣告 1 + 出队即记 7 + 完成 1（没有返回拍）

看点在队列条的滚动：输出条下方有一排队列格，出队的节点落进输出条、它的孩子从队尾排进来——[5] → [3,8] → [1,4,7,9] → …。队列长度在"换层"前达到峰值，这一眼能直接看到"一层最多能有多少个节点"。

动画怎么看

上半区是树：7 个节点盒 + 父子实线连线；黄色描边 = 当前出队的节点，访问过的节点转绿色常驻；
队列条：输出条下方一排格子实时显示队列内容——头在左，出队从头部弹出，孩子从尾部入队，头出尾进一目了然；
出队拍：队头节点被记录进输出条、转绿，同拍状态行显示 第k个访问 v ｜出队 v · 入队 a b；
口诀立牌：左上角常驻「口诀逐层左→右」+ 副注「队列 FIFO · 头出尾进」；
大✓：✓ 完成｜层次遍历 7 节点全部输出，全程 9 拍——比 DFS 三兄弟少在没有返回拍：队列替你记住了"接下来该看谁"，不需要回溯。

复杂度分析

项目	复杂度	说明
时间	O(n)	每个节点恰好出队、入队各一次
空间	O(n)	队列峰值 = 最宽一层的节点数，最坏（完全二叉树底层）≈ n/2
对比 DFS	O(h)	DFS 递归栈只有树高；宽树用层次遍历更费空间，深树则相反
层边界技巧	O(n)	记录"本层剩余计数"或每层先取 `queue.len()`，即可按层切开处理

C++ 参考代码

#include <iostream>
#include <queue>
struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void levelOrder(Node *root) {
    if (!root) return;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *cur = q.front(); q.pop();     // 头出
        std::cout << cur->val << " ";       // 记录
        if (cur->left)  q.push(cur->left);  // 尾进：先左
        if (cur->right) q.push(cur->right); //       后右
    }
}

int main() {
    // 完全 BST：5(3(1,4), 8(7,9))
    Node a(1), b(4), c(3), d(7), e(9), f(8), root(5);
    c.left = &a; c.right = &b;
    f.left = &d; f.right = &e;
    root.left = &c; root.right = &f;
    levelOrder(&root);                      // 输出 5 3 8 1 4 7 9
    return 0;
}

什么时候用层次遍历

凡是**"按层"或"最短"语义的问题都用它：逐层打印 / 锯齿形打印（每层切开后还能反转方向）、树的最小深度（第一次碰到叶子就是最浅——DFS 必须走完全部路径才能比较）、二叉树的右视图 / 每层最大值 / 层平均值（都是"每层取一个统计量"）、以及在无权图上求最短路径**（BFS 的本行，首次到达即最少步数）。和 DFS 三兄弟的根本分工一句话说清：要距离/层次用队列（层次遍历），要路径/结构用递归（先中后序）——动画里那条不断滚动的队列，就是把"接下来按什么顺序看"从递归栈搬到了明面上。