102.二叉树的层序遍历

107.二叉树的层次遍历II

199.二叉树的右视图

637.二叉树的层平均值

429.N叉树的层序遍历

515.在每个树行中找最大值

116.填充每个节点的下一个右侧节点指针

117.填充每个节点的下一个右侧节点指针II

104.二叉树的最大深度

111.二叉树的最小深度

参考：代码随想录

102.二叉树的层序遍历

链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

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

题解：队列驱动+逐层收集节点值

在二叉树遍历中，"迭代法"指的是使用循环结构（如 while/for）和显式的数据结构（如队列） 来实现遍历，而不是通过函数递归调用（递归法）

工作流程

1.在每层开始时：记录队列当前长度len

这个值就是当前层所有节点的数量，此时队列中的节点全部属于同一层

2.处理当前层：执行len次循环

每次循环处理一个节点节点出队时，将其子节点加入队列 (这些子节点属于下一层)

3.自然切换层级：当1en减到0时

当前层所有节点处理完毕，队列中剩下的全是新加入的子节点(即下一层节点)，自动切换到下一层的处理

class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {checkFun02(root);return resList;}public void checkFun02(TreeNode node) {if (node == null) return;//头出尾入的双端队列Queue<TreeNode> que = new LinkedList<TreeNode>();//根节点入队que.offer(node);//外层循环：处理每一层while (!que.isEmpty()) {//存储当前层所有节点值List<Integer> itemList = new ArrayList<Integer>();//当前层节点的数量int len = que.size();//内层循环：处理当前层所有的节点while (len > 0) {//1.队头出队TreeNode tmpNode = que.poll();//2.记录节点值itemList.add(tmpNode.val);//3.子节点入队（先左后右）if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);//当前层节点计数器减去1len--;}//整层节点值存入结果resList.add(itemList);}
}

107.二叉树的层次遍历II

链接：107. 二叉树的层序遍历 II - 力扣（LeetCode）

题目：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题解：

public class N0107 {/*** 解法：队列，迭代。* 层序遍历，再翻转数组即可。*/public List<List<Integer>> solution1(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {List<Integer> levelList = new ArrayList<>();int levelSize = que.size();for (int i = 0; i < levelSize; i++) {TreeNode peek = que.peekFirst();levelList.add(que.pollFirst().val);if (peek.left != null) {que.offerLast(peek.left);}if (peek.right != null) {que.offerLast(peek.right);}}list.add(levelList);}List<List<Integer>> result = new ArrayList<>();for (int i = list.size() - 1; i >= 0; i-- ) {result.add(list.get(i));}return result;}
}

199.二叉树的右视图

链接：199. 二叉树的右视图 - 力扣（LeetCode）

题目：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

题解：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，放入result数组种，随后返回result.

public class N0199 {/*** 解法：队列，迭代。* 每次返回每层的最后一个字段即可。** 小优化：每层右孩子先入队。代码略。*/public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize = que.size();for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}if (i == levelSize - 1) {list.add(poll.val);}}}return list;}
}

637.二叉树的层平均值

链接：637. 二叉树的层平均值 - 力扣（LeetCode）

题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

题解：层序遍历的时候把一层求个总和再取个均值。

public class N0637 {/*** 解法：队列，迭代。* 每次返回每层的最后一个字段即可。*/public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize = que.size();double levelSum = 0.0;for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();levelSum += poll.val;if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}}list.add(levelSum / levelSize);}return list;}
}

429.N叉树的层序遍历

链接：429. N 叉树的层序遍历 - 力扣（LeetCode）

题目：

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

题解：一个节点有多个孩子

public class N0429 {/*** 解法1：队列，迭代。*/public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> list = new ArrayList<>();Deque<Node> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize = que.size();List<Integer> levelList = new ArrayList<>();for (int i = 0; i < levelSize; i++) {Node poll = que.pollFirst();levelList.add(poll.val);List<Node> children = poll.children;if (children == null || children.size() == 0) {continue;}for (Node child : children) {if (child != null) {que.offerLast(child);}}}list.add(levelList);}return list;}class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}}
}

515.在每个树行中找最大值

链接：515. 在每个树行中找最大值 - 力扣（LeetCode）

题目：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

题解：层序遍历，取每层的最大值。

class Solution {public List<Integer> largestValues(TreeNode root) {if(root == null){return Collections.emptyList();}List<Integer> result = new ArrayList();Queue<TreeNode> queue = new LinkedList();queue.offer(root);while(!queue.isEmpty()){int max = Integer.MIN_VALUE;for(int i = queue.size(); i > 0; i--){TreeNode node = queue.poll();max = Math.max(max, node.val);if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);}result.add(max);}return result;}
}

116.填充每个节点的下一个右侧节点指针

链接：116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

题目：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

题解：依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {public Node connect(Node root) {Queue<Node> tmpQueue = new LinkedList<Node>();if (root != null) tmpQueue.add(root);while (tmpQueue.size() != 0){int size = tmpQueue.size();Node cur = tmpQueue.poll();if (cur.left != null) tmpQueue.add(cur.left);if (cur.right != null) tmpQueue.add(cur.right);for (int index = 1; index < size; index++){Node next = tmpQueue.poll();if (next.left != null) tmpQueue.add(next.left);if (next.right != null) tmpQueue.add(next.right);cur.next = next;cur = next;}}return root;}
}

117.填充每个节点的下一个右侧节点指针II

链接：117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

题目：

给定一个二叉树：
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

题解：

class Solution {public Node connect(Node root) {Queue<Node> queue = new LinkedList<>();if (root != null) {queue.add(root);}while (!queue.isEmpty()) {int size = queue.size();Node node = null;Node nodePre = null;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = queue.poll(); // 取出本层头一个节点node = nodePre;} else {node = queue.poll();nodePre.next = node; // 本层前一个节点 next 指向当前节点nodePre = nodePre.next;}if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}nodePre.next = null; // 本层最后一个节点 next 指向 null}return root;}
}

104.二叉树的最大深度

链接：104. 二叉树的最大深度 - 力扣（LeetCode）

题目：

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

题解：二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。最大的深度就是二叉树的层数。

class Solution {public int maxDepth(TreeNode root) {if (root == null)   return 0;Queue<TreeNode> que = new LinkedList<>();que.offer(root);int depth = 0;while (!que.isEmpty()){int len = que.size();while (len > 0){TreeNode node = que.poll();if (node.left != null)  que.offer(node.left);if (node.right != null) que.offer(node.right);len--;}depth++;}return depth;}
}

111.二叉树的最小深度

链接：111. 二叉树的最小深度 - 力扣（LeetCode）

题目：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

题解：当左右孩子都为空的时候，说明遍历到最低点了。

class Solution {public int minDepth(TreeNode root){if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()){int size = queue.size();depth++;TreeNode cur = null;for (int i = 0; i < size; i++) {cur = queue.poll();//如果当前节点的左右孩子都为空，直接返回最小深度if (cur.left == null && cur.right == null){return depth;}if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}}return depth;}
}