建设微网站项目报告网站专题分类

建设微网站项目报告,网站专题分类,wamp网站开发视频教程,湛江免费做网站目录 一、基础#xff1a;LeetCode 102. 二叉树的层序遍历#xff08;普通层序#xff09; 1. 核心思想#xff1a;队列控层 左→右入队 2. 完整实现代码 3. 重点 难点 二、变种#xff1a;LeetCode 103. 二叉树的锯齿形层序遍历 1. 核心思想#xff1a;普通…目录一、基础LeetCode 102. 二叉树的层序遍历普通层序1. 核心思想队列控层 左→右入队2. 完整实现代码3. 重点 难点二、变种LeetCode 103. 二叉树的锯齿形层序遍历1. 核心思想普通层序 按层反转2. 完整实现代码3. 重点 难点三、进阶LeetCode 513. 找二叉树最底层最左节点1. 核心思想两种解法解法 1你的思路逆序层序 取最后一个元素解法 2普通层序 取最后一层第一个元素3. 重点 难点四、三道题核心对比五、层序遍历类题通用易错点六、深度总结层序遍历广度优先搜索 BFS是二叉树的核心遍历方式其核心逻辑是 “队列控层 按层处理”。以下总结普通层序遍历、锯齿形层序遍历、找最底层最左节点三道题覆盖核心思路、实现、重难点及深度对比。一、基础LeetCode 102. 二叉树的层序遍历普通层序1. 核心思想队列控层 左→右入队层序遍历的 “模板级” 题目核心是通过队列记录节点并通过 “每层节点数” 控制遍历边界保证 “按层输出”队列初始化根节点入队按层遍历每次遍历前记录队列大小当前层节点数遍历完该层所有节点后再处理下一层子节点入队始终 “先左后右”保证每层节点按 “左→右” 顺序输出。2. 完整实现代码class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) return result; // 边缘情况空树直接返回 QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); // 关键记录当前层节点数 ListInteger 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 ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) return result; QueueTreeNode queue new LinkedList(); queue.offer(root); boolean needReverse false; // 标记当前层是否需要反转 while (!queue.isEmpty()) { int levelSize queue.size(); ListInteger 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) { ListInteger result new ArrayList(); QueueTreeNode 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) { ListListInteger levelList new ArrayList(); QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); ListInteger 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. 重点 难点重点“最底层最左” 的两种实现思路逆序入队用 “右→左” 入队让左节点最后被记录按层存储用二维列表定位 “最后一层第一个”难点理解 “层序遍历的顺序” 和 “节点位置” 的关联 —— 层序遍历是 “从上到下、从左到右”最底层的节点一定是最后遍历的最左节点是该层第一个 / 最后一个取决于入队顺序。四、三道题核心对比维度普通层序遍历102锯齿形层序遍历103找最底层最左节点513核心目标按层输出所有节点左→右按层交替反转输出节点定位 “最底层最左” 节点子节点入队顺序先左后右先左后右仅结果反转解法 1先右后左解法 2先左后右结果处理直接按层存入二维列表按层反转后存入二维列表解法 1一维列表取最后一个解法 2二维列表取最后层第一个空间复杂度O(n)O(n)解法 1O (n)解法 2O (n)略高核心技巧队列控层levelSize结果反转Collections.reverse入队顺序 / 按层存储的灵活应用五、层序遍历类题通用易错点遗漏空节点判断子节点入队前未判断!null导致空指针异常队列控层错误在遍历层内节点时用queue.size()而非遍历前的levelSize队列大小会随入队变化混淆 “入队顺序” 和 “结果顺序”锯齿形遍历中试图通过改变入队顺序实现反转导致后续层遍历混乱边缘情况处理忽略rootnull的情况导致空树时代码崩溃。六、深度总结层序遍历的核心本质是 “队列控层 按层处理”所有变种题的解题关键固定层边界必须用levelSize queue.size()在遍历层前记录节点数这是层序遍历的 “基石”灵活调整入队顺序 / 结果处理普通层序先左后右入队直接记录结果锯齿形先左后右入队结果按层反转找最底层最左要么逆序入队要么按层存储后定位空间优化能不用二维列表就不用如 513 的解法 1但优先保证逻辑清晰。