【LeetCode刷题日记】一口气搞定三道层序遍历！从N叉树到二叉树，BFS核心思想一网打尽

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

这一章节我们继续刷二叉树的层序遍历的相关题目。

摘要：

本文探讨了二叉树层序遍历的三种变式问题：N叉树层序遍历、每层最大值查找和填充右节点指针。对于N叉树，通过遍历子节点列表替代二叉树的左右节点判断；查找每层最大值时需注意负数情况；填充右指针则通过记录前驱节点建立连接。三种解法均基于队列实现层序遍历，核心思想相似但处理细节不同。文章提供了Java代码实现，并强调了不同数据结构间的处理差异，展示了层序遍历的灵活应用。

题目背景：492.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]之间

题目分析：

关于这一题，我们拿到题目一眼就是层序遍历，因为题目的要求就是，我们很自然的想到了前面我们学习的二叉树的层序遍历，这里有点不一样，但是整体思路肯定是一样的，不必多说，那么变化的地方肯定就在不一样的地方了，原来的是 二叉树，而这里是N，所以代码主要变化的就是这一部分。

然后我们分析每个根节点有两个子节点（左右节点）和每个根节点有N个子节点的具体差别。首先根节点的遍历没问题，在进入while循环时，我们把每层的节点记录到一个集合中，之后我们在二叉树中是通过两个条件判断来添加左右子节点的，这里显然就不行了，我们不知道有多少个子节点，这是又需要一个循环了

本质是一样的，只是表达方式不同

所以N叉树的这个for循环，等价于二叉树的这两行：

java

if (node.left != null) queue.offer(node.left); // 处理左子节点 if (node.right != null) queue.offer(node.right); // 处理右子节点

只是因为N叉树的子节点数量不固定（可能有0个、2个、5个、10个...），所以必须用循环遍历children列表，把每一个子节点都加入队列。

text

二叉树： 1 / \ 2 3 处理节点1时： - 判断 left(2) != null → 入队 - 判断 right(3) != null → 入队 → 一共2次判断 N叉树： 1 / | \ 2 3 4 处理节点1时： - 遍历 children = [2,3,4] - 2入队，3入队，4入队 → 一共3次入队（次数取决于子节点数量）

两者做的是一模一样的事：把当前节点的所有非空子节点加入队列，供下一层遍历使用。

题目答案：

/* // Definition for a Node. 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; } }; */ class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result=new ArrayList<>(); if(root==null){ return result; } Queue<Node> que=new LinkedList<>(); que.offer(root); while(!que.isEmpty()){ List<Integer> level=new ArrayList<>(); int len=que.size(); for(int i=0;i<len;i++){ Node node=que.poll(); level.add(node.val); for(Node child:node.children){ if(child!=null){ que.offer(child); } } } result.add(level); } return result; } }

题目背景：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

题目分析：

这个题目也是在层序遍历的基础上进行的变式，我们要求的是每层的最大值，首先就要把每层的节点数记录下来，然后遍历每一层的节点，在循环中更新每一层的最大值，之后添加到结果集。

maxVal = Math.max(maxVal, node.val);，这里我们一开始设置的最大值的初值不能是0，因为节点可能会有负数，因此，我们设置，Integer.MIN_VALUE = -2147483648。

题目答案：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> largestValues(TreeNode root) { 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(); int maxVal = Integer.MIN_VALUE; // 因节点可能为负数，不能用0 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); maxVal = Math.max(maxVal, node.val); // 将子节点加入队列（与N叉树的区别：二叉树只有左右两个子节点） if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(maxVal); } return result; } }

题目背景：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 = []输出：[]

题目解析：

这道题目实际上是链表的相关操作，通过指针，把同一层的不相干的节点建立了联系，

"记录位置"	prev = curr	记住当前节点在哪，下次要用
"构建关系"	prev.next = curr	让上一个节点指向当前节点

两个动作配合：

1. 先用prev记住上一个节点的位置

2. 再用prev找到上一个节点，建立连接

3. 然后prev移到当前位置，准备下一次连接

prev = null → 手里没东西 遇到第1家 A：prev = A （记住A的位置） 遇到第2家 B：用记住的A位置，告诉A"你的下一家是B" prev = B （改为记住B的位置） 遇到第3家 C：用记住的B位置，告诉B"你的下一家是C" prev = C （改为记住C的位置）

题目答案：

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public Node connect(Node root) { if(root==null){ return null; } Queue<Node> que=new LinkedList<>(); que.offer(root); while(!que.isEmpty()){ int len=que.size(); Node pre=null; for(int i=0;i<len;i++){ Node cur=que.poll(); if(pre!=null){ pre.next=cur; } pre=cur; if(cur.left!=null){ que.offer(cur.left); que.offer(cur.right); } } } return root; } }

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！