102.二叉树的层序遍历
给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000
解题思路1
用一个全局列表 ans 表示所有层，其中 ans.get(deep) 对应第 deep 层的节点值集合。每次递归时，deep 表示当前节点所在的层号（从 0 开始）。如果 ans 的大小不足以容纳当前层（即 ans.size() < deep + 1），就添加一个新的空列表。然后将当前节点的值加入对应层的列表中。
代码1
class Solution {
// 定义一个全局的 List<List<Integer>> 用于存储层序遍历的结果，每一层是一个 List<Integer>
List<List<Integer>> ans = new ArrayList<>();
// 主方法，接收二叉树的根节点，返回层序遍历结果
public List<List<Integer>> levelOrder(TreeNode root) {
Integer deep = 0; // 初始化深度为 0，表示从根节点所在的第 0 层开始
fun1(root, deep); // 调用辅助方法 fun1 开始递归遍历
return ans; // 返回最终的层序遍历结果
}
// 辅助方法，使用递归按深度填充每一层的节点值
public void fun1(TreeNode root, Integer deep) {
if (root == null) { // 如果当前节点为空，直接返回（递归的终止条件）
return;
}
// 检查当前深度是否超出现有层数，如果是，则添加一个新的空列表表示新的一层
if (ans.size() < deep + 1) {
ans.add(new ArrayList<>()); // 为新的一层创建一个独立的 ArrayList
}
// 将当前节点的值添加到对应深度的列表中
ans.get(deep).add(root.val);
// 递归处理左子树，深度加 1（进入下一层）
fun1(root.left, deep + 1);
// 递归处理右子树，深度加 1（进入下一层）
fun1(root.right, deep + 1);
}
}解题思路2
队列遵循“先进先出”（FIFO）的特性，先将根节点入队，然后逐层处理节点。每处理一层时，记录当前队列大小（即该层节点数），依次移除每个节点并访问，同时将其左右子节点加入队列，为下一层做准备。
代码2
class Solution {
// 定义全局结果列表，存储层序遍历的每一层节点值
List<List<Integer>> ans = new ArrayList<>();
// 定义队列，用于按层存储待处理的节点
Queue<TreeNode> queue = new ArrayDeque<>();
// 主方法，接收二叉树根节点，返回层序遍历结果
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) { // 如果根节点为空，直接返回空的结果列表
return ans;
}
queue.offer(root); // 将根节点加入队列，作为第一层开始
while (!queue.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = queue.size(); // 获取当前层的节点数量
List<Integer> list = new ArrayList<>(); // 创建当前层的节点值列表
while (len > 0) { // 遍历当前层的所有节点
TreeNode node = new TreeNode(); // 创建一个新节点（多余，稍后改进）
node = queue.poll(); // 从队列头部移除并获取当前节点（覆盖上面的新节点）
list.add(node.val); // 将当前节点值加入当前层列表
if (node.left != null) queue.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) queue.offer(node.right); // 如果有右子节点，加入队列
len--; // 当前层节点计数减 1
}
ans.add(list); // 当前层处理完毕，将其加入结果列表
}
return ans; // 返回完整的层序遍历结果
}
}107.二叉树的层序遍历2
给你二叉树的根节点
root，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]示例 2：
输入：root = [1] 输出：[[1]]示例 3：
输入：root = [] 输出：[]提示：
- 树中节点数目在范围
[0, 2000]内-1000 <= Node.val <= 1000
解题思路
- 先用标准的层序遍历（BFS）从顶向下获取所有层的节点值，存储在 ans 中，结果是从根到叶子的顺序（[[3], [9, 20], [15, 7]]）。
- 使用 Collections.reverse() 将 ans 反转，变成从叶子到根的顺序（[[15, 7], [9, 20], [3]]）。
代码
class Solution {
// 标准层序遍历（从顶向下）
private List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>(); // 局部变量，避免状态残留
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new ArrayDeque<>(); // 局部队列
queue.offer(root);
while (!queue.isEmpty()) {
int len = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < len; i++) { // 用 for 循环替代 while
TreeNode node = queue.poll(); // 直接获取节点
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
ans.add(list);
}
return ans;
}
// 自底向上层序遍历
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = levelOrder(root); // 获取从顶向下的结果
Collections.reverse(result); // 反转列表，实现自底向上
return result;
}
}199.二叉树的右视图
给定一个二叉树的 根节点
root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
- 二叉树的节点个数的范围是
[0,100]-100 <= Node.val <= 100
解题思路
- 通过深度参数（deep）跟踪当前节点所在的层号。
- 对于每一层，优先保留最右侧节点的值。递归时先访问左子树，再访问右子树，这样右子树的值会覆盖同一层的左子树值。
- list 的索引对应层号，list.get(deep) 表示第 deep 层的最右侧节点值。
代码
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>(); // 局部变量，避免状态残留
fun1(root, 0, list); // 传入 list 作为参数
return list;
}
private void fun1(TreeNode root, int deep, List<Integer> list) {
if (root == null) { // 空节点返回
return;
}
// 确保 list 大小足够当前深度
while (list.size() <= deep) {
list.add(0); // 添加默认值（可以优化）
}
list.set(deep, root.val); // 设置当前深度的值（右子树会覆盖左子树）
fun1(root.left, deep + 1, list); // 先递归左子树
fun1(root.right, deep + 1, list); // 后递归右子树（右子树值保留）
}
}429.N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示：
- 树的高度不会超过
1000- 树的节点总数在
[0, 104]之间
解题思路
- 队列遵循“先进先出”（FIFO）特性，先将根节点入队，然后逐层处理节点。
- 每处理一层时，记录当前队列大小（len），依次移除每个节点，访问其值，并将其所有子节点加入队列，为下一层做准备。
代码
class Solution {
// 主方法，返回 N 叉树的层序遍历结果
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ans = new ArrayList<>(); // 存储每层节点值的列表
if (root == null) { // 如果根节点为空，返回空结果
return ans;
}
Queue<Node> queue = new ArrayDeque<>(); // 创建队列用于 BFS
queue.offer(root); // 将根节点加入队列，作为第一层
while (!queue.isEmpty()) { // 当队列不为空时，继续处理
int len = queue.size(); // 获取当前层的节点数量
List<Integer> list = new ArrayList<>(); // 存储当前层的节点值
for (int i = 0; i < len; i++) { // 遍历当前层的所有节点
Node node = queue.poll(); // 从队列头部移除并获取当前节点
list.add(node.val); // 将节点值加入当前层列表
for (Node child : node.children) { // 遍历当前节点的所有子节点
if (child != null) { // 检查子节点非空
queue.offer(child); // 将子节点加入队列，准备下一层
}
}
}
ans.add(list); // 当前层处理完毕，加入结果列表
}
return ans; // 返回完整的层序遍历结果
}
}637.二叉树的层平均值
给定一个非空二叉树的根节点
root, 以数组的形式返回每一层节点的平均值。与实际答案相差10-5以内的答案可以被接受。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]提示：
- 树中节点数量在
[1, 104]范围内-231 <= Node.val <= 231 - 1
解题思路
- 层序遍历部分：使用递归方法 fun1，以深度参数（deep）追踪当前节点所在的层号。全局列表 ans 存储每一层的节点值，ans.get(deep) 表示第 deep 层的节点值集合。递归时，先访问当前节点并记录值，再处理左子树和右子树，通过深度确保节点值按层组织。
- 平均值计算部分：在 averageOfLevels 中，遍历 ans 的每一层，使用 long 变量 sum 累加该层节点值，然后除以节点数（list1.size()）得到平均值，结果以 double 类型存储在 ave 中。
- 执行流程：从根节点开始（deep = 0），递归填充 ans，完成后遍历 ans 计算每层平均值，最终返回 ave。
代码
class Solution {
List<List<Integer>> ans = new ArrayList<>(); // 定义全局列表，存储每层的节点值
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ave = new ArrayList<>(); // 定义结果列表，存储每层的平均值
levelOrder(root); // 调用层序遍历方法，填充 ans
for (List<Integer> list1 : ans) { // 遍历每一层的节点值列表
long sum = 0; // 初始化当前层的总和
for (int i = 0; i < list1.size(); i++) { // 遍历当前层的所有节点值
sum += (Integer) list1.get(i); // 累加节点值到 sum
}
ave.add((double) sum / list1.size()); // 计算当前层平均值并加入结果
}
return ave; // 返回每层平均值的列表
}
public List<List<Integer>> levelOrder(TreeNode root) {
Integer deep = 0; // 初始化深度为 0，表示根节点层
fun1(root, deep); // 调用递归方法，开始层序遍历
return ans; // 返回层序遍历结果
}
public void fun1(TreeNode root, Integer deep) {
if (root == null) { // 如果当前节点为空，返回
return;
}
if (ans.size() < deep + 1) { // 如果当前深度超出 ans 大小
ans.add(new ArrayList<>()); // 为新层添加一个空列表
}
ans.get(deep).add(root.val); // 将当前节点值加入对应层的列表
fun1(root.left, deep + 1); // 递归处理左子树，深度加 1
fun1(root.right, deep + 1); // 递归处理右子树，深度加 1
}
}104.二叉树的最大深度
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2提示：
- 树中节点的数量在
[0, 104]区间内。-100 <= Node.val <= 100
解题思路
利用队列的“先进先出”（FIFO）特性，按层遍历二叉树。每处理完一层，深度计数器 length 增加 1，最终 length 表示从根节点到最远叶子节点的层数，即最大深度。
代码
class Solution {
Deque<TreeNode> deque = new ArrayDeque<>(); // 定义双端队列，用于存储待处理的节点
int length = 0; // 定义变量，记录二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null) { // 如果根节点为空，返回深度 0
return 0;
}
deque.offer(root); // 将根节点加入队列，作为第一层
while (!deque.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = deque.size(); // 获取当前层的节点数量
length++; // 每处理一层，深度加 1
while (len > 0) { // 遍历当前层的所有节点
TreeNode node = new TreeNode(); // 创建一个新节点（占位）
node = deque.poll(); // 从队列头部移除并获取当前节点
len--; // 当前层节点计数减 1
if (node.left != null) deque.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) deque.offer(node.right); // 如果有右子节点，加入队列
}
}
return length; // 返回二叉树的最大深度
}
}111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5提示：
- 树中节点数的范围在
[0, 105]内-1000 <= Node.val <= 1000
解题思路
利用队列的“先进先出”（FIFO）特性，按层遍历二叉树，从根节点开始逐层检查。当遇到第一个叶子节点（没有子节点的节点）时，返回当前深度 length，即为最小深度。
代码
class Solution {
Deque<TreeNode> deque = new ArrayDeque<>(); // 定义双端队列，用于存储待处理的节点
int length = 0; // 定义变量，记录当前处理的深度
public int minDepth(TreeNode root) {
if (root == null) { // 如果根节点为空，返回深度 0
return 0;
}
deque.offer(root); // 将根节点加入队列，作为第一层
while (!deque.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = deque.size(); // 获取当前层的节点数量
length++; // 每处理一层，深度加 1
while (len > 0) { // 遍历当前层的所有节点
TreeNode node = new TreeNode(); // 创建一个新节点（占位）
node = deque.poll(); // 从队列头部移除并获取当前节点
len--; // 当前层节点计数减 1
if (node.left == null && node.right == null) { // 如果当前节点是叶子节点
return length; // 返回当前深度作为最小深度
}
if (node.left != null) deque.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) deque.offer(node.right); // 如果有右子节点，加入队列
}
}
return length; // 返回最终深度
}
}116.填充每一个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。示例 1：
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2:
输入：root = [] 输出：[]提示：
- 树中节点的数量在
[0, 212 - 1]范围内-1000 <= node.val <= 1000进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
解题思路
利用队列的“先进先出”（FIFO）特性，按层遍历二叉树。在每一层中，将当前节点的 next 指针设置为队列中的下一个节点（即右侧节点），从而连接同一层的节点。
代码
class Solution {
Deque<Node> deque = new ArrayDeque(); // 定义双端队列，用于存储待处理的节点
public Node connect(Node root) {
if (root == null) { // 如果根节点为空，返回 null
return root;
}
deque.offer(root); // 将根节点加入队列，作为第一层
while (!deque.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = deque.size(); // 获取当前层的节点数量
while (len > 0) { // 遍历当前层的所有节点
Node node = new Node(); // 创建一个新节点（占位）
node = deque.poll(); // 从队列头部移除并获取当前节点
len--; // 当前层节点计数减 1
if (node.left != null) deque.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) deque.offer(node.right); // 如果有右子节点，加入队列
if (len != 0) node.next = deque.peek(); // 如果不是当前层最后一个节点，设置 next 指向队列头部节点
}
}
return root; // 返回填充了 next 指针的根节点
}
}117.填充每一个节点的下一个右侧节点指针2
给定一个二叉树：
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。示例 1：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。示例 2：
输入：root = [] 输出：[]提示：
- 树中的节点数在范围
[0, 6000]内-100 <= Node.val <= 100进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
解题思路
利用队列的“先进先出”（FIFO）特性，按层遍历二叉树。在每一层中，将当前节点的 next 指针设置为队列中的下一个节点（即右侧节点），从而连接同一层的节点。
代码
class Solution {
Deque<Node> deque = new ArrayDeque(); // 定义双端队列，用于存储待处理的节点
public Node connect(Node root) {
if (root == null) { // 如果根节点为空，返回 null
return root;
}
deque.offer(root); // 将根节点加入队列，作为第一层
while (!deque.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = deque.size(); // 获取当前层的节点数量
while (len > 0) { // 遍历当前层的所有节点
Node node = new Node(); // 创建一个新节点（占位）
node = deque.poll(); // 从队列头部移除并获取当前节点
len--; // 当前层节点计数减 1
if (node.left != null) deque.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) deque.offer(node.right); // 如果有右子节点，加入队列
if (len != 0) node.next = deque.peek(); // 如果不是当前层最后一个节点，设置 next 指向队列头部节点
}
}
return root; // 返回填充了 next 指针的根节点
}
}515.在每个树行中找最大值
给定一棵二叉树的根节点
root，请找出该二叉树中每一层的最大值。示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]示例2：
输入: root = [1,2,3] 输出: [1,3]提示：
- 二叉树的节点个数的范围是
[0,104]-231 <= Node.val <= 231 - 1
解题思路
利用队列的“先进先出”（FIFO）特性，按层遍历二叉树。在每一层中，遍历所有节点，比较它们的值，记录最大值，并在层结束时加入结果列表。
代码
class Solution {
List<Integer> ans = new ArrayList<>(); // 定义全局列表，存储每层的最大值
Deque<TreeNode> queue = new ArrayDeque<>(); // 定义双端队列，用于存储待处理的节点
public List<Integer> largestValues(TreeNode root) {
if (root == null) { // 如果根节点为空，返回空列表
return ans;
}
queue.offer(root); // 将根节点加入队列，作为第一层
while (!queue.isEmpty()) { // 当队列不为空时，继续处理每一层
int len = queue.size(); // 获取当前层的节点数量
TreeNode node = new TreeNode(); // 创建一个新节点（占位）
List<Integer> list = new ArrayList<>(); // 创建列表（未使用）
Integer max = Integer.MIN_VALUE; // 初始化当前层最大值为最小整数
while (len > 0) { // 遍历当前层的所有节点
node = queue.poll(); // 从队列头部移除并获取当前节点
if (node.val > max) { // 如果当前节点值大于 max
max = node.val; // 更新最大值
}
len--; // 当前层节点计数减 1
if (node.left != null) queue.offer(node.left); // 如果有左子节点，加入队列
if (node.right != null) queue.offer(node.right); // 如果有右子节点，加入队列
}
ans.add(max); // 将当前层的最大值加入结果列表
}
return ans; // 返回每层最大值的列表
}
}