二叉树的层序遍历

层序遍历（Level Order Traversal）是一种广度优先搜索（BFS）策略，用于按层级顺序访问二叉树中的每个节点。具体来说，它从根节点开始，自上而下、自左而右地逐层遍历所有节点。这种遍历方式在解决如“二叉树的最大深度”、“二叉树的最小深度”、“判断二叉树是否对称”等问题时非常有用。

1. 核心思想与基本步骤

层序遍历的核心思想是使用队列（Queue）这一数据结构来辅助实现。队列的先进先出（FIFO）特性恰好符合按层级顺序访问节点的需求。基本步骤如下：

1. 初始化：将根节点加入队列。
2. 循环处理队列：只要队列不为空，重复以下步骤：
   • 从队列中取出当前节点（即队首节点），访问该节点（如打印其值）。
   • 如果当前节点有左子节点，将左子节点加入队列。
   • 如果当前节点有右子节点，将右子节点加入队列。
3. 终止条件：当队列为空时，说明所有节点都已处理完毕。

2. 详细过程示例

假设有如下二叉树：

       1
      / \
     2   3
    / \   \
   4   5   6

层序遍历的结果应为：1, 2, 3, 4, 5, 6。

逐步模拟过程：

• 步骤1：初始队列为 [1]。
  • 取出节点1，访问节点1（输出 1）。
  • 将节点1的左子节点2和右子节点3加入队列，队列变为 [2, 3]。
• 步骤2：队列非空，取出节点2，访问节点2（输出 2）。
  • 将节点2的左子节点4和右子节点5加入队列，队列变为 [3, 4, 5]。
• 步骤3：取出节点3，访问节点3（输出 3）。
  • 将节点3的右子节点6加入队列，队列变为 [4, 5, 6]。
• 步骤4：取出节点4，访问节点4（输出 4）。节点4无子节点，队列变为 [5, 6]。
• 步骤5：取出节点5，访问节点5（输出 5）。节点5无子节点，队列变为 [6]。
• 步骤6：取出节点6，访问节点6（输出 6）。节点6无子节点，队列变为空。
• 终止：队列为空，遍历结束。最终输出顺序为 1, 2, 3, 4, 5, 6。

3. 代码实现（伪代码）

以通用编程语言风格描述算法逻辑：

层序遍历(根节点 root):
    如果 root 为空，直接返回
    初始化队列 queue，将 root 加入队列
    当 queue 不为空时：
        当前节点 node = 取出队首元素
        访问 node 的值
        如果 node 有左子节点，将左子节点加入队列
        如果 node 有右子节点，将右子节点加入队列

4. 常见变体：按层分组输出

有时面试会要求将每一层的节点值分别输出为单独的列表（例如 LeetCode 题目“二叉树的层序遍历”）。此时需稍作调整：

• 在每一层开始前，记录当前队列的长度（即该层节点数）。
• 通过循环处理完当前层的所有节点，并将它们的值存入一个临时列表。
• 将临时列表加入结果集，再继续处理下一层。

调整后的伪代码：

层序遍历分组(根节点 root):
    如果 root 为空，返回空列表
    初始化队列 queue，将 root 加入队列
    初始化结果列表 result
    当 queue 不为空时：
        当前层节点数 level_size = queue 的当前长度
        初始化当前层列表 level_list
        重复 level_size 次：
            节点 node = 取出队首元素
            将 node 的值加入 level_list
            如果 node 有左子节点，加入队列
            如果 node 有右子节点，加入队列
        将 level_list 加入 result
    返回 result

对于上述示例二叉树，分组输出结果为：[[1], [2, 3], [4, 5, 6]]。

5. 时间复杂度与空间复杂度

• 时间复杂度：O(n)，其中 n 为节点数，每个节点恰好被访问一次。
• 空间复杂度：O(n)，队列中最多同时存储一层节点，最坏情况下（平衡二叉树）约为 O(n) 级别。

通过以上步骤，你可以掌握层序遍历的基本原理、实现细节及其常见应用场景。