二叉树的层序遍历-编程实验室

二叉树是数据结构中至关重要的非线性结构，而层序遍历（Level Order Traversal）是二叉树遍历方式中极具代表性的一种 —— 它按照从上到下、从左到右的顺序逐层访问节点，这种遍历方式也被称为 “广度优先遍历（BFS）”。本文将从层序遍历的核心思想出发，拆解具体实现逻辑，并通过完整代码解析，带你掌握二叉树层序遍历的实现方法。

一、层序遍历的核心思想

不同于前序、中序、后序遍历的 “深度优先” 思路（沿着一条路径走到头再回溯），层序遍历的核心是 “广度优先”：先访问根节点所在的第一层，再依次访问第二层的所有节点，接着是第三层…… 直到遍历完所有层级。

要实现这种 “逐层访问” 的逻辑，关键在于借助队列（Queue）这一数据结构。队列的 “先进先出（FIFO）” 特性，恰好能满足 “先访问的节点，其左右子节点也先入队、先被访问” 的需求：

初始化队列，将根节点入队；
循环处理队列中的节点：每次取出当前队列中的所有节点（即当前层的全部节点），记录它们的值，再将这些节点的左右子节点（非空时）依次入队；
重复上述过程，直到队列为空，此时所有层级已遍历完毕。

二、完整代码实现与逐行解析

以下是基于 C++ 实现的二叉树层序遍历代码，我们将逐行拆解核心逻辑：

cpp

运行

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { // 存储最终结果，每一个子数组对应一层的节点值 vector<vector<int>> result; // 空树直接返回空结果，避免后续无效操作 if (root == nullptr) return result; // 队列存储待遍历的节点，核心数据结构 queue<TreeNode*> q; // 根节点入队，作为遍历的起点 q.push(root); // 队列非空时，说明还有未遍历的节点 while (!q.empty()) { // 关键：记录当前层的节点数量（队列此时的大小即为当前层节点数） int levelSize = q.size(); // 存储当前层的所有节点值 vector<int> currentLevel; // 遍历当前层的所有节点 for (int i = 0; i < levelSize; i++) { // 取出队列头部节点（当前层的下一个节点） TreeNode* node = q.front(); q.pop(); // 记录当前节点值到当前层的结果中 currentLevel.push_back(node->val); // 左子节点非空则入队，为下一层遍历做准备 if (node->left != nullptr) { q.push(node->left); } // 右子节点非空则入队，保持“左到右”的顺序 if (node->right != nullptr) { q.push(node->right); } } // 将当前层的结果加入最终结果集 result.push_back(currentLevel); } return result; } };

核心细节拆解

空树判断：代码开头先判断根节点是否为空，若为空直接返回空的结果数组，这是鲁棒性的体现，避免后续对空指针的操作。
队列的作用：队列是层序遍历的核心，它始终存储 “下一层待遍历的节点”。每次进入while循环时，队列的大小恰好等于当前层的节点数量 —— 这是实现 “分层” 的关键。
分层遍历的关键：levelSize = q.size()这一行是整个代码的精髓。因为进入while循环时，队列中所有节点都属于同一层，通过levelSize限定for循环的次数，就能确保每次for循环只处理当前层的节点，不会混入下一层的节点。
子节点入队顺序：先左子节点、后右子节点入队，保证了遍历结果符合 “从左到右” 的层序要求。

三、代码执行流程示例

假设我们有一棵简单的二叉树：

plaintext

3 / \ 9 20 / \ 15 7

代码的执行流程如下：

初始化队列，将根节点 3 入队，队列：[3]；
进入while循环，levelSize=1，开启for循环（i=0）：
- 取出节点 3，记录值 3，当前层数组：[3]；
- 节点 3 的左子节点 9、右子节点 20 入队，队列变为：[9,20]；
- for循环结束，将 [3] 加入结果集，结果：[[3]]；
再次进入while循环，队列非空，levelSize=2，开启for循环：
- i=0：取出节点 9，记录值 9，当前层数组：[9]；节点 9 无左右子节点，队列变为：[20]；
- i=1：取出节点 20，记录值 20，当前层数组：[9,20]；节点 20 的左子节点 15、右子节点 7 入队，队列变为：[15,7]；
- for循环结束，将 [9,20] 加入结果集，结果：[[3],[9,20]]；
再次进入while循环，队列非空，levelSize=2，开启for循环：
- i=0：取出节点 15，记录值 15，当前层数组：[15]；节点 15 无左右子节点，队列变为：[7]；
- i=1：取出节点 7，记录值 7，当前层数组：[15,7]；节点 7 无左右子节点，队列变为空；
- for循环结束，将 [15,7] 加入结果集，结果：[[3],[9,20],[15,7]]；
队列为空，while循环结束，返回最终结果。

四、时间与空间复杂度分析

时间复杂度：O (n)。其中 n 是二叉树的节点总数。每个节点仅入队和出队一次，遍历所有节点的时间复杂度为 O (n)，其余操作（如记录节点值）均为常数级。
空间复杂度：O (n)。最坏情况下（如满二叉树），队列需要存储最后一层的所有节点，最后一层的节点数最多为 n/2，因此空间复杂度为 O (n)。