leetcode102：二叉树的层序遍历（队列实现）

文章目录

• 一、题目描述
• 二、 核心思路：队列 (Queue) 实现 BFS
• 三、 代码实现与深度解析
• 四、 关键点与复杂度分析

二叉树遍历中的另一种重要遍历方式——层序遍历，对应的就是 LeetCode 102. 二叉树的层序遍历 - 力扣（LeetCode）【难度：中；通过率：70.0%】

层序遍历与我们之前接触的前序、中序、后序遍历（深度优先搜索 DFS）不同，它属于广度优先搜索 (BFS) 的范畴，代码并不涉及“递归”，所以理论上是更好且更容易理解

一、题目描述

给你二叉树的根节点 root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）

示例:

输入: root = [3,9,20,null,null,15,7]输出: [[3],[9,20],[15,7]]

二、 核心思路：队列 (Queue) 实现 BFS

层序遍历的核心思想是：一层一层地访问节点。这与队列（Queue）的“先进先出”特性完美契合

具体步骤如下：

1. 初始化：
   • 创建一个 List<List> 来存储最终结果，其中每个 List 代表一层
   • 创建一个 Queue，用于存储待访问的节点
2. 起始：将根节点 root 加入队列
3. 循环遍历：
   • 当队列不为空时，循环继续
   • 获取当前层的节点数量：在每次循环开始时，记录下当前队列中元素的数量 len = queue.size()。这个 len 就是当前层的所有节点数
   • 遍历当前层：使用一个 for 循环，迭代 len 次：
     • 从队列中取出一个节点 node
     • 将 node.val 加入到当前层的结果列表中
     • 如果 node 有左孩子，将 node.left 加入队列
     • 如果 node 有右孩子，将 node.right 加入队列
   • 当前层的所有节点处理完毕后，将当前层的结果列表加入到最终结果列表中

三、 代码实现与深度解析

【一种参考代码】：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { // 二叉树的层序遍历 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); // 存储最终结果，每个子列表代表一层 // 如果根节点为空，直接返回空列表，因为没有节点可以遍历 if (root == null) { return res; } // 主要用增删操作，我们选择 LinkedList 作为 Queue 的实现 // Queue 是一个接口，LinkedList 实现了它，提供了队列的特性（先进先出，FIFO） Queue<TreeNode> queue = new LinkedList<>();  // 将根节点加入队列，作为层序遍历的起点 queue.add(root); // 当队列不为空时，循环继续，表示还有节点待访问 while (!queue.isEmpty()) { // 创建一个列表来存储当前层的所有节点值 List<Integer> level = new ArrayList<>();// 记录当前队列的大小，这个大小就是当前层的节点数量 // 关键点：在开始遍历当前层之前固定住这一层的节点数量 int currentLevelSize = queue.size(); // 遍历当前层的所有节点 for (int i = 0; i < currentLevelSize; i++) { // 从队列头部取出节点（先进先出） TreeNode node = queue.poll(); // 将当前节点的值加入到当前层的列表中 // 由于我们已经处理了 root == null 的情况，并且只在 node 不为 null 时才加入其子节点， // 所以这里的 node 理论上不会是 null level.add(node.val); // 如果当前节点有左孩子，将其加入队列尾部，等待下一轮（下一层）处理 if (node.left != null) {  queue.add(node.left); } // 如果当前节点有右孩子，将其加入队列尾部，等待下一轮（下一层）处理 if (node.right != null) {  queue.add(node.right); } } // 当前层的所有节点都已处理完毕并加入 level 列表，将其添加到最终结果中 res.add(level); }  // 返回包含所有层节点值的列表 return res; }}

四、 关键点与复杂度分析

• 广度优先搜索 (BFS)：层序遍历是 BFS 在二叉树上的应用。BFS 的核心是使用队列
• 队列的作用：队列用于存储“下一批要访问的节点”。它确保我们总是先访问同一层的节点，然后才进入下一层
• 分层处理的技巧：在 while 循环内部，通过 int currentLevelSize = queue.size(); 来锁定当前层的节点数量，然后通过一个 for 循环精确地处理当前层的所有节点，这是实现按层输出的关键
• 时间复杂度：O(N) 其中 N 是二叉树的节点数。每个节点都会被访问一次，并被加入和移出队列一次
• 空间复杂度：O(W) 其中 W 是二叉树的最大宽度。在最坏情况下（例如，满二叉树的最后一层），队列中可能会存储大约 N/2 个节点，所以空间复杂度可以认为是 O(N)

道德经全文