知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 二叉树的层序遍历 ## 题目(LeetCode 102) 给你一棵二叉树,返回其按层序遍历得到的节点值(逐层从左到右)。 ``` 3 / \ 9 20 / \ 15 7 输出:[[3], [9, 20], [15, 7]] ``` ## 大白话理解 一层一层地从上往下、从左往右读。就像你看一栋楼,先看第一层有什么,再看第二层,再看第三层…… 核心工具:队列(Queue)。 为什么用队列?因为队列是先进先出(FIFO),正好符合"先处理上层,再处理下层"的顺序。 ``` 处理过程: 队列状态 操作 结果 [3] 弹出 3,加入 9 和 20 第 1 层:[3] [9, 20] 弹出 9(无子节点) [20] 弹出 20,加入 15 和 7 第 2 层:[9, 20] [15, 7] 弹出 15,弹出 7 第 3 层:[15, 7] [] 队列空,结束 ``` 关键技巧:怎么知道一层结束了?每次循环开始时记录队列大小 `size`,弹出 `size` 个节点就是一层。 ## 代码 ```java 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 size = queue.size(); // 当前层有几个节点 List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { // 只处理当前层 TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; } ``` ## 变体题目 层序遍历是一个模板,稍微改一下就能解很多题: ```java // 自底向上层序遍历(LeetCode 107) // 最后 Collections.reverse(result) 或者每次 result.add(0, level) // 锯齿形层序遍历(LeetCode 103) // 奇数层正序,偶数层反序 boolean leftToRight = true; for (...) { if (leftToRight) level.add(node.val); else level.add(0, node.val); // 头插 } leftToRight = !leftToRight; // 二叉树的右视图(LeetCode 199) // 每层只取最后一个节点 if (i == size - 1) result.add(node.val); // 每层的最大值(LeetCode 515) // 每层遍历时维护 max // 每层的平均值(LeetCode 637) // 每层求和再除以 size ``` ## 复杂度 - 时间:O(n) - 空间:O(w),w 是树的最大宽度(队列中最多存一层的节点) ## 一句话总结 队列 + 每次循环处理一层(用 size 控制),这个模板能解一堆层序相关的题。 --- 上一篇:[07 - 最近公共祖先](./07-lowest-common-ancestor.md) | 下一篇:[09 - 从前序与中序构造二叉树](./09-build-tree.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入