102. 二叉树的层序遍历（中等）

Blind 75 › 102. 二叉树的层序遍历（中等） （第 6 章）
文章工具

题目

给定一棵二叉树的根节点 root，请按“一层一层、每层从左到右”的顺序，把每一层的节点值收集成一个列表，最后返回所有层的列表。

换句话说：第 0 层只有根节点；第 1 层是根节点的所有孩子（按从左到右）；第 2 层是这些孩子的所有孩子（同样从左到右）……每一层单独放进一个数组。

自造示例：root = [5,1,8,null,3,7,9]，其中 5 的左孩子是 1、右孩子是 8；1 只有右孩子 3；8 的左孩子是 7、右孩子是 9。返回 [[5],[1,8],[3,7,9]]。

约束：节点数 0 ~ 2000；节点值 -1000 ~ 1000；空树 root = [] 应返回 []。

思路

一句话：用队列做 BFS，处理每一层前先记下“当前队列长度”，这个长度就是本层的节点数，按批出队即可。

先想最直白的：直接做一次普通的 BFS，不分组，得到的只是扁平序列 [5,1,8,3,7,9]。它丢掉了“这一层在哪里结束、下一层从哪里开始”的信息，不符合“按层返回”的要求。

另一个直白写法是 DFS：递归时多传一个深度 depth，把节点值放进 res[depth]。它能过，但“层”是靠额外的深度参数硬切出来的，不如 BFS 直观。

关键观察：BFS 队列天然“一层接一层”地进出。开始处理某一层时，队列里恰好全是这一层的节点，而且按从左到右排列。所以只要在每轮循环开头记下 size = q.size()，就知道本层要处理几个；把这 size 个节点出队、并顺手把孩子入队后，队列里剩下的又恰好是下一层的全部节点。

于是选 BFS + 每轮固定队列长度：一次遍历，层与层之间靠“批次大小”自然切分。

解法

  1. 若 root 为空，直接返回空列表。
  2. 队列初始为 [root]。
  3. 只要队列非空：记 size = q.size()，新建本层列表 level。
  4. 循环 size 次：出队一个节点，把值放进 level；若左孩子非空则入队，若右孩子非空则入队。
  5. 把 level 追加到结果，进入下一轮处理下一层。

以自造示例走一遍：

轮次处理前队列size本轮收集处理后队列
1[5]1[5][1, 8]
2[1, 8]2[1, 8][3, 7, 9]
3[3, 7, 9]3[3, 7, 9][]

队列为空时结束，三个桶依次就是三层。

下图把上面 5 个步骤串成流程，并逐步演示：

102. 二叉树的层序遍历（中等） 解法步骤流程图
图① 解法步骤流程图（共 5 步）。
102. 二叉树的层序遍历（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
/**
 * 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) return result;  queue<TreeNode*> q;
 q.push(root);  while (!q.empty()) {
 int size = q.size();          // 本层节点数，先固定住
 vector<int> level;
 level.reserve(size);
 for (int i = 0; i < size; ++i) {
 TreeNode* node = q.front();
 q.pop();
 level.push_back(node->val);
 if (node->left)
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。