0102.二叉树的层序遍历
难度：🟡 中等
标签：树、广度优先搜索、二叉树
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[1](./1.md)
示例 3：
输入：root = []
输出：[]
解题思路
核心思想
本题要求按层级顺序遍历二叉树，这正是 广度优先搜索（Breadth-First Search, BFS） 的典型应用。BFS 的核心是使用一个队列（Queue）来实现逐层探索。从根节点开始，我们先访问根节点，然后将其所有子节点加入队列，再依次从队列中取出节点进行访问，并将其子节点加入队列，如此循环往复，直到队列为空。
思路选择
使用队列实现广度优先搜索是解决此问题的最标准、最高效的思路。为了将每一层的节点值分组到不同的子数组中，我们可以在每一轮的遍历开始前，记录下当前队列中的节点数量 levelSize，这个数量就是当前层所包含的节点总数。然后，我们只对这 levelSize 个节点进行出队操作，从而确保每一轮循环处理的都是同一层的节点。
关键步骤
处理边界情况：如果根节点
root为空，直接返回空数组[]。初始化：创建一个队列
queue并将根节点root入队。创建一个结果数组results用于存放最终的层序遍历结果。开始循环：当
queue不为空时，持续进行层序遍历。分层处理： a. 在循环的开始，获取当前
queue的长度levelSize。这代表了当前层级的节点总数。 b. 创建一个临时数组currentLevel，用于存放当前层所有节点的值。 c. 启动一个内层循环，执行levelSize次。 d. 在内层循环中，从queue的头部取出一个节点（出队）。 e. 将该节点的值存入currentLevel数组。 f. 如果该节点有非空的左子节点，将其左子节点入队。 g. 如果该节点有非空的右子节点，将其右子节点入队。存储层级结果：内层循环结束后，
currentLevel数组就包含了当前层所有的节点值。将其推入results数组。返回结果：当外层
while循环结束时（即队列为空），results中就包含了完整的层序遍历结果，返回results即可。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (root === null) {
return [];
}
const queue = [root]; // 初始化队列，并将根节点入队
const results = []; // 存放最终结果
while (queue.length > 0) {
const levelSize = queue.length; // 当前层的节点数
const currentLevel = []; // 存放当前层节点值的数组
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // 节点出队
currentLevel.push(node.val);
// 将下一层的节点入队
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
results.push(currentLevel); // 将当前层的结果推入最终结果集
}
return results;
};
复杂度分析
时间复杂度：O(n) 其中 n 是树中节点的总数。每个节点都会被访问（入队和出队）一次。
空间复杂度：O(w) 其中 w 是树的最大宽度。空间复杂度主要取决于队列中存储的节点数。在最坏的情况下（一个完美的完全二叉树），队列中最多会存储最后一层的所有节点，约为 n/2 个，因此空间复杂度可以认为是 O(n)。
相关题目
0107.二叉树的层序遍历 II (自底向上的层序遍历)
总结
本题是二叉树广度优先搜索（BFS）的模板题。其核心是利用队列“先进先出”的特性来保证按层级顺序访问节点。通过在每一轮循环开始时固定当前层的节点数量，可以巧妙地将不同层的节点分离开来，这是处理层序遍历问题的一个通用且高效的技巧。