【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叉树子节点存储方式两个单独的变量left和right一个列表children入队操作分别判断left和right是否非空遍历列表把每个子节点入队本质把子节点加入队列把子节点加入队列所以N叉树的这个for循环等价于二叉树的这两行javaif (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 ListNode children; public Node() {} public Node(int _val) { val _val; } public Node(int _val, ListNode _children) { val _val; children _children; } }; */ class Solution { public ListListInteger levelOrder(Node root) { ListListInteger resultnew ArrayList(); if(rootnull){ return result; } QueueNode quenew LinkedList(); que.offer(root); while(!que.isEmpty()){ ListInteger levelnew ArrayList(); int lenque.size(); for(int i0;ilen;i){ Node nodeque.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 ListInteger largestValues(TreeNode root) { ListInteger resultnew ArrayList(); if (root null) { return result; } QueueTreeNode 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让上一个节点指向当前节点两个动作配合先用prev记住上一个节点的位置再用prev找到上一个节点建立连接然后prev移到当前位置准备下一次连接prev null → 手里没东西 遇到第1家 Aprev 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(rootnull){ return null; } QueueNode quenew LinkedList(); que.offer(root); while(!que.isEmpty()){ int lenque.size(); Node prenull; for(int i0;ilen;i){ Node curque.poll(); if(pre!null){ pre.nextcur; } precur; if(cur.left!null){ que.offer(cur.left); que.offer(cur.right); } } } return root; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励