LeetCode 102/103/513 二叉树层序遍历（BFS）三类经典题解题总结

目录

一、基础：LeetCode 102. 二叉树的层序遍历（普通层序）

1. 核心思想：队列控层 + 左→右入队

2. 完整实现代码

3. 重点 & 难点

二、变种：LeetCode 103. 二叉树的锯齿形层序遍历

1. 核心思想：普通层序 + 按层反转

2. 完整实现代码

3. 重点 & 难点

三、进阶：LeetCode 513. 找二叉树最底层最左节点

1. 核心思想（两种解法）

解法 1：你的思路（逆序层序 + 取最后一个元素）

解法 2：普通层序 + 取最后一层第一个元素

3. 重点 & 难点

四、三道题核心对比

五、层序遍历类题通用易错点

六、深度总结

层序遍历（广度优先搜索 BFS）是二叉树的核心遍历方式，其核心逻辑是 “队列控层 + 按层处理”。以下总结普通层序遍历、锯齿形层序遍历、找最底层最左节点三道题，覆盖核心思路、实现、重难点及深度对比。

一、基础：LeetCode 102. 二叉树的层序遍历（普通层序）

1. 核心思想：队列控层 + 左→右入队

层序遍历的 “模板级” 题目，核心是通过队列记录节点，并通过 “每层节点数” 控制遍历边界，保证 “按层输出”：

• 队列初始化：根节点入队；
• 按层遍历：每次遍历前记录队列大小（当前层节点数），遍历完该层所有节点后，再处理下一层；
• 子节点入队：始终 “先左后右”，保证每层节点按 “左→右” 顺序输出。

2. 完整实现代码

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; // 边缘情况：空树直接返回 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // 关键：记录当前层节点数 List<Integer> currentLevel = new ArrayList<>(); // 遍历当前层的所有节点 for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); currentLevel.add(cur.val); // 子节点先左后右入队（保证层内顺序） if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } result.add(currentLevel); // 记录当前层结果 } return result; } }

3. 重点 & 难点

• 重点：levelSize = queue.size()是层序遍历的 “灵魂”—— 通过固定当前层节点数，避免不同层节点混在一起遍历；
• 难点：理解 “队列的先进先出” 如何适配 “按层遍历”：队列中始终只存 “下一层待遍历的节点”，遍历完当前层后，队列恰好是下一层的所有节点。

二、变种：LeetCode 103. 二叉树的锯齿形层序遍历

1. 核心思想：普通层序 + 按层反转

锯齿形遍历的本质是 “普通层序遍历的结果加工”，而非 “改变遍历顺序”：

• 先按 “普通层序（左→右）” 遍历，记录每一层的节点值；
• 根据层数奇偶性，决定是否反转当前层的节点列表（偶数层反转，奇数层不反转）；
• 核心：子节点仍 “先左后右” 入队（保证下一层遍历顺序正确），仅对当前层结果做反转。

2. 完整实现代码

class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean needReverse = false; // 标记当前层是否需要反转 while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); currentLevel.add(cur.val); // 子节点仍先左后右入队（关键！不打乱下一层顺序） if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } // 按层反转：偶数层（从0开始）反转，奇数层不反转 if (needReverse) Collections.reverse(currentLevel); result.add(currentLevel); needReverse = !needReverse; // 切换下一层的反转状态 } return result; } }

3. 重点 & 难点

• 重点：不要试图通过 “改变子节点入队顺序” 实现锯齿形 —— 这会打乱下一层的遍历逻辑，导致结果错误；
• 难点：层数奇偶性的判断（从 0 开始还是从 1 开始）：
  • 若第一层（根节点）不反转，needReverse初始为false；
  • 每遍历完一层，切换needReverse状态。

三、进阶：LeetCode 513. 找二叉树最底层最左节点

1. 核心思想（两种解法）

解法 1：你的思路（逆序层序 + 取最后一个元素）

• 核心：调整子节点入队顺序为 “先右后左”，让每一层的节点按 “右→左” 记录，最终结果列表的最后一个元素就是 “最底层最左节点”；
• 优点：空间更省（仅需一维列表），代码简洁；
• 完整代码（你的优化版）

class Solution { public int findBottomLeftValue(TreeNode root) { List<Integer> result = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); result.add(cur.val); // 先右后左入队，让左节点最后被记录 if (cur.right != null) queue.offer(cur.right); if (cur.left != null) queue.offer(cur.left); } } return result.get(result.size() - 1); // 最后一个元素是最底层最左 } }

解法 2：普通层序 + 取最后一层第一个元素

• 核心：按 “普通层序（左→右）” 遍历，用二维列表存储每一层的节点值，最终取最后一层列表的第一个元素；
• 优点：逻辑直观（符合常规层序思维）；但需要设置两个列表
• 完整代码：

class Solution { public int findBottomLeftValue(TreeNode root) { List<List<Integer>> levelList = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode cur = queue.poll(); currentLevel.add(cur.val); // 普通层序：先左后右入队 if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } levelList.add(currentLevel); } // 取最后一层的第一个元素 return levelList.get(levelList.size() - 1).get(0); } }

3. 重点 & 难点

• 重点：“最底层最左” 的两种实现思路：
  • 逆序入队：用 “右→左” 入队让左节点最后被记录；
  • 按层存储：用二维列表定位 “最后一层第一个”；
• 难点：理解 “层序遍历的顺序” 和 “节点位置” 的关联 —— 层序遍历是 “从上到下、从左到右”，最底层的节点一定是最后遍历的，最左节点是该层第一个 / 最后一个（取决于入队顺序）。

四、三道题核心对比

五、层序遍历类题通用易错点

1. 遗漏空节点判断：子节点入队前未判断!=null，导致空指针异常；
2. 队列控层错误：在遍历层内节点时，用queue.size()而非遍历前的levelSize（队列大小会随入队变化）；
3. 混淆 “入队顺序” 和 “结果顺序”：锯齿形遍历中试图通过改变入队顺序实现反转，导致后续层遍历混乱；
4. 边缘情况处理：忽略root==null的情况，导致空树时代码崩溃。

六、深度总结

层序遍历的核心本质是 “队列控层 + 按层处理”，所有变种题的解题关键：

1. 固定层边界：必须用levelSize = queue.size()在遍历层前记录节点数，这是层序遍历的 “基石”；
2. 灵活调整入队顺序 / 结果处理：
   • 普通层序：先左后右入队，直接记录结果；
   • 锯齿形：先左后右入队，结果按层反转；
   • 找最底层最左：要么逆序入队，要么按层存储后定位；
3. 空间优化：能不用二维列表就不用（如 513 的解法 1），但优先保证逻辑清晰。

   ---