推广网络网站,数字营销是什么专业,牡丹江建设厅网站,wordpress 密码生成文章目录 前言1. 层次遍历介绍2. 基本的层次遍历与变换2.1 二叉树的层次遍历2.2 层次遍历-自底向上2.3 二叉树的锯齿形层次遍历2.4 N叉树的层次遍历 3. 几个处理每层元素的题目3.1 在每棵树行中找出最大值3.2 在每棵树行中找出平均值3.3 二叉树的右视图3.4 最底层最左边 总结 前… 文章目录 前言1. 层次遍历介绍2. 基本的层次遍历与变换2.1 二叉树的层次遍历2.2 层次遍历-自底向上2.3 二叉树的锯齿形层次遍历2.4 N叉树的层次遍历 3. 几个处理每层元素的题目3.1 在每棵树行中找出最大值3.2 在每棵树行中找出平均值3.3 二叉树的右视图3.4 最底层最左边 总结 前言 提示这个世界上的任何一次拥抱都是将以松手告终。 --约瑟夫·布罗茨基《悲伤与理智》 二叉树的层次遍历是一个非常简单的问题但是很多人没有接触过所以就认为很难面试的时候当然就写不出来了今天我们就重点通关层次遍历这个问题。 1. 层次遍历介绍
广度优先在面试中属于常考类型整体来说属于简单次但是很多人面试遇到了就放弃真的很可惜。我们就看看它的难度在哪里。
广度优先又叫做层次遍历基本过程如下 层次遍历就是从根节点开始先访问根节点的一层全部元素在访问之后的一层类似金字塔一样一层一层访问。我们可以看做就是从左到右的一层一层去遍历二叉树先访问5之后访问3的左右孩子4 和 6 之后再访问4 和 6的孩子1 2 和 7 8。最后得到结果【5461278】
这里的问题就变成了将遍历过的子孩子保存下来比如访问4 的左右孩子1 和 2 的时候应该先存储直到处理完20之后再处理。使用队列的话就可以解决上述问题。
看下过程图解
根节点入队 5然后 5 出队 之后将 5 的左右孩子4 6入队保存在队列中4 出队将4 的左右孩子 1 2 入队之后 6 出队将 6 的左右孩子 7 8 入队保存在队列中最终 1 2 7 8 依次出队此时都是叶子几点只要出队就行了。
这个过程不复杂如果将树的每层分开是不是可以整活了首先能否将每层的元素顺序反转一下或者说奇数不变偶数反转是否将输出层次从低到高root输出呢再比如既然可以拿到每层的元素能不能找到当前层最大的元素最小的元素呢最右端的元素右视图最左端的元素左视图整个层的平均值当然这都是可以实现的嘞这么来回折腾有啥用呢没啥用了但是这些都是层次遍历的高频算法题目。
推荐力扣题目⭐⭐⭐⭐
102. 二叉树的层序遍历 - 力扣LeetCode
107. 二叉树的层序遍历 II - 力扣LeetCode
199. 二叉树的右视图 - 力扣LeetCode
637. 二叉树的层平均值 - 力扣LeetCode
429. N 叉树的层序遍历 - 力扣LeetCode
515. 在每个树行中找最大值 - 力扣LeetCode
116. 填充每个节点的下一个右侧节点指针 - 力扣LeetCode
117. 填充每个节点的下一个右侧节点指针 II - 力扣LeetCode
103. 二叉树的锯齿形层序遍历 - 力扣LeetCode
2. 基本的层次遍历与变换
我们看一个最简单的情况仅仅是遍历并输出全部元素如下图 上图的输入结果【54678】方法已经梳理过了这里看一下代码怎么实现。先访问根节点然后其左右孩子入队接着出队出队的元素将其左右孩子入队直到队列为空就可以退出了 /*** 二叉树层序遍历* param root* return*/public static ListInteger simpleLevelOrder(TreeNode root) {// 参数校验if (root null) {return new ArrayListInteger();}// 创建存储空间ListInteger res new ArrayListInteger();LinkedListTreeNode queue new LinkedListTreeNode();// 根节点先入队queue.add(root);// 遍历队列元素while(queue.size() 0){// 获取当前队列的长度这个长度相当于这一层的节点个数TreeNode t queue.remove();res.add(t.val);if (t.left ! null){queue.add(t.left);}if (t.right ! null){queue.add(t.right);}}return res;}注意:
根据树的结构可以看出一个节点在一层访问之后其子孩子都是在下层按照FIFO的顺序处理的因此队列在这里起到了一个缓存的作用。
如果要你将每层的元素分开该怎么做呢?看下下面的这个题
2.1 二叉树的层次遍历
题目介绍102. 二叉树的层序遍历 - 力扣LeetCode 我们再来看这个执行过程我们先将根节点放入队列中然后不断的遍历队列。 那如何判断某一层访问完了呢这个简单我们用一个size标记一下就行了size表示某一层元素的个数知道出队size就减1减到0就说明该层访问完了当size变成0之后这时队列中甚于元素个数恰好就是下一次的个数因此重新将size标记为下一层的元素个数就可以继续处理新的一行例如上面的序列中
首先获取根节点 3 左右子节点不为空将左右子节点放入队列此时3 已经出队。剩下的9 20 恰好是第二层的所有节点此时size 2继续将9 出队左右节点不为空将左右节点放入队列size-- 变成 1 之后将20 出队左右节点不为空将左右节点放入队列 size– 变为 0。当size 0说明当前层已经处理完了此时队列有4个元素恰好是下一层的元素个数。最后我们把每层遍历到的节点放入一个结果集中将其返回就可以了
按层次遍历经典代码 /*** 层次遍历 经典方式* param root* return*/public static ListListInteger level102Order(TreeNode root) {// 校验参数if (root null){return new ArrayListListInteger();}// 创建空间ListListInteger res new ArrayListListInteger();LinkedListTreeNode queue new LinkedListTreeNode();// 将根节点放入队列 然后不断遍历队列queue.add(root);while(queue.size() 0){// 获取当前size的个数 即当前层有多少个元素int size queue.size();// 创建临时空间 将一层的元素存入其中ListInteger temp new ArrayListInteger();for(int i 0; i size; i){TreeNode t queue.remove();temp.add(t.val);if (t.left ! null){queue.add(t.left);}if (t.right ! null){queue.add(t.right);}}// 此时的temp就是一层的所有元素用list类型保存temp最后加入到结果集中res.add(temp);}return res;}此方法一定要牢记在算法体系中是很重要的一环他与链表反转二分查找可以相提并论务必掌握彻底理解然后记忆。
当然上面的算法理解了下面的一系列题目都变得简单了不信你往下看。
注意:
在Java中队列的实现不止一种需要注意。
2.2 层次遍历-自底向上
题目介绍107. 二叉树的层序遍历 II - 力扣LeetCode 如果要求从上到下输出每一层的节点值做法很直观在遍历完一层之后将该层存储节点值的列表添加到结果集的尾部。这道题要求从下到上输出每一层的节点值只要对上述操作稍作修改就可以了在遍历完一层节点后将存储该层节点值的列表添加到结果集的头部。
为了降低在结果列表的头部添加一层节点值的列表的时间复杂度结果列表可以使用链表的结构在链表头部添加一层节点值的列表的时间复杂度为O(1)在Java中由于我们需要返回一个List接口在这里可以使用链表实现。
代码就很普通了 /*** 层序遍历 自底向上* param root* return*/public static ListListInteger levelOrderBottom(TreeNode root) {// 校验参数if (root null){return new ArrayListListInteger();}// 创建空间ListListInteger levelOrder new LinkedListListInteger();QueueTreeNode queue new LinkedListTreeNode();// 根节点存入队列中 不断的遍历queue.offer(root);while(queue.size() 0){ListInteger level new ArrayListInteger();int size queue.size();for(int i 0; i size; i){TreeNode node queue.poll();level.add(node.val);// 这样也行TreeNode left node.left,right node.right;if(left ! null){queue.offer(left);}if (right ! null){queue.offer(right);}}levelOrder.add(0,level); // 放在头部 栈}return levelOrder;}2.3 二叉树的锯齿形层次遍历
题目介绍103. 二叉树的锯齿形层序遍历 - 力扣LeetCode 这个题也是102. 二叉树的层序遍历 - 力扣LeetCode的变种只是最后输出的要求变化了要求我们按照层数的奇偶来决定每层输出的顺序如果当前是偶数层从左到右输出当前层的节点值否则从右至左输出当前层的节点值。这里我们同样可以采用102的方法思想。
但是为了满足条件【左右-右左】交替暑促的锯齿形可以利用【双端队列】的数据机构来维护当前节点值的输出顺序。双端队列是一个可以在队列任意一端插入元素的队列。在广度优先遍历搜索当前节点扩展下一层节点的时候我们仍然可以从左往右循序扩展但是对于当前层节点的存储我们维护一个变量isOrderLeft记录时从左到右还是从右到左
如果从左到右我们每次将被遍历的元素插入到双端队列的末尾从右到左我们每次将被遍历的元素插入到双端队列的头部。
代码展示
/*** 锯齿层次遍历* param root* return*/public static ListListInteger zigzagLevelOrder(TreeNode root) {// 校验参数if (root null){return new ArrayListListInteger();}// 创建空间ListListInteger ans new LinkedListListInteger();QueueTreeNode queue new LinkedListTreeNode();// 将根节点放入队列 不断循环遍历queue.offer(root);// 判断奇偶变量boolean isOrderLeft true;while(queue.size() 0){// 这里要使用双端队列DequeInteger temp new LinkedListInteger();int size queue.size();for(int i 0; i size; i){TreeNode t queue.poll();if (isOrderLeft){temp.offerLast(t.val);}else{temp.offerFirst(t.val);}if (t.left ! null){queue.offer(t.left);}if (t.right ! null){queue.offer(t.right);}}ans.add(new LinkedListInteger(temp));isOrderLeft !isOrderLeft;}return ans;}2.4 N叉树的层次遍历
题目介绍429. N 叉树的层序遍历 - 力扣LeetCode 首先看下N叉树的结构就是一个值的不同变成了以一个列表其类型仍然时Node
class TreeNode {public int val;public ListTreeNode children;}也就是说我们可以说这个也是102. 二叉树的层序遍历 - 力扣LeetCode的变种我们就用简单的广度优先借助队列即可实现。 /*** N 叉树的遍历* param root* return*/public static ListListInteger nLevelOrder(NTreeNode root) {// 校验参数if (root null){return new ArrayListListInteger();}// 创建空间ListListInteger res new ArrayListListInteger();DequeNTreeNode queue new ArrayDequeNTreeNode();// 根节点放入队列 不断遍历queue.offer(root);while(!queue.isEmpty()){DequeNTreeNode next new ArrayDeque();ListInteger level new ArrayList();while(!queue.isEmpty()){NTreeNode current queue.pollFirst();level.add(current.val);// 注意这里链表遍历for (NTreeNode child : current.children){if (child ! null){next.add(child);}}}// 重新定义queuequeue next;res.add(level);}return res;}3. 几个处理每层元素的题目
如果我们拿到每一层的元素那么是不是可以利用一下就可以造几个题目出来呢例如每层找最大的值平均值最右侧的值当然可以。这也是力扣的上面比较经典的题目了
题目推荐⭐⭐⭐⭐
515. 在每个树行中找最大值 - 力扣LeetCode
637. 二叉树的层平均值 - 力扣LeetCode
199. 二叉树的右视图 - 力扣LeetCode
当然我们自己也可以造题目比如说层次取最小值可以吗每层的最左侧值可以不是不是现在发现算法其实很好玩的
3.1 在每棵树行中找出最大值
题目介绍515. 在每个树行中找最大值 - 力扣LeetCode 这里其实就是得到一层之后使用一个变量来记录当前的最大值
代码也很简单 /*** 层序遍历找到每层最大值* param root* return*/public static ListInteger largestValues(TreeNode root) {// 校验参数if(root null){return new ArrayListInteger();}// 创建空间ListInteger res new ArrayListInteger();DequeTreeNode queue new ArrayDequeTreeNode();// 根节点入队不断循环遍历queue.offer(root);while(queue.size() 0){int size queue.size();int maxLevel Integer.MIN_VALUE;for(int i 0; i size; i){TreeNode t queue.poll();maxLevel Math.max(maxLevel, t.val);if (t.left ! null){queue.offer(t.left);}if (t.right ! null){queue.offer(t.right);}}res.add(maxLevel);}return res;}3.2 在每棵树行中找出平均值
题目介绍637. 二叉树的层平均值 - 力扣LeetCode 这个题目和前面的一样之不多每层都先将元素保存下来最后求一个平均值就可以了是不是是很简单 /*** 层序遍历求出每层平均值* param root* return*/public static ListDouble averageOfLevels(TreeNode root) {// 检验参数if(root null){return new ArrayListDouble();}// 创建空间ListDouble res new ArrayListDouble();QueueTreeNode queue new LinkedListTreeNode();// 根节点入队不断循环queue.offer(root);while(queue.size() 0){int size queue.size();double sum 0;for(int i 0; i size; i ){TreeNode t queue.poll();sum t.val;if (t.left ! null){queue.offer(t.left);}if (t.right ! null){queue.offer(t.right);}}res.add(sum/size);}return res;}3.3 二叉树的右视图
题目介绍199. 二叉树的右视图 - 力扣LeetCode 这个题目说实话出频率还挺高的如果没有提前思考过很难想到答案。其实也简单在BFS进行层次遍历的时候记录下每层的最后一个元素就可以了。 /*** 层序遍历输出右视图* param root* return*/public static ListInteger rightSideView(TreeNode root) {// 校验参数if(root null){return new ArrayListInteger();}// 创建空间ListInteger res new ArrayListInteger();QueueTreeNode queue new LinkedListTreeNode();// 根节点入队不断循环遍历queue.offer(root);while(!queue.isEmpty()){int size queue.size();for(int i 0; i size; i){TreeNode t queue.poll();if (t.left ! null){queue.offer(t.left);}if (t.right ! null){queue.offer(t.right);}// 这里将最后一个节点放入结果集中if (i size - 1){res.add(t.val);}}}return res;}是不是有点成就感了感觉算法是有套路的并不是四刷题目。这三道题基本上都是层序遍历的变种。
那我我们也可以尝试着造出题目来
有右视图那么左视图行不行俯视图行不行想一下
嘿嘿我这里告诉你吧俯视图不行但是左视图可以想下为什么
3.4 最底层最左边
题目介绍513. 找树左下角的值 - 力扣LeetCode 在第二部分我们写了很多层次遍历的变种形式这里有两个问题:
该怎么知道什么时候到最底层了加入最底层有两个该怎么知道那个时最左的呢
带着这两个问题我们再看下层序遍历的执行过程 我们可以发现正常执行层次遍历的不管最底层有几个元素最后输出的一定是底层最右的元素7这里我们就想象一下可不可以和上面题目一样结合反转操作实现呢每一层先反转再存入队列到最后是不是输出的为最左节点值呢是的知道了这个解题关键点我想答案你已经会写了。 public int findBottomLeftValue(TreeNode root) {// 校验参数if(root.left null root.right null){return root.val;}// 创建空间QueueTreeNode queue new LinkedListTreeNode();// 根节点入队不断循环遍历queue.offer(root);TreeNode temp new TreeNode();while(!queue.isEmpty()){temp queue.poll();// 先右后左 if(temp.right ! null){queue.offer(temp.right);}if(temp.left ! null){queue.offer(temp.left);}}return temp.val;}总结
提示二叉树的层序遍历各种变种问题熟练掌握模板题总结套路是不是感觉算法也是有迹可循的
