当前位置: 首页 > news >正文

算法通关村第六关|白银|二叉树的层次遍历【持续更新】

1.二叉树基本的层序遍历

仅仅遍历并输出全部元素。

List<Integer> simpleLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}List<Integer> res = new ArrayList<Integer>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();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;
}

2.二叉树层序遍历,但是按层分开

用 size 标记。

public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) {return new ArrayList<List<Integer>>();}List<List<Integer>> res = new ArrayList<List<Integer>>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while (queue.size() > 0) {// 获取当前层的元素个数int size = queue.size();ArrayList<Integer> temp = new ArrayList<Integer>();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);}}res.add(temp);}return res;
}

3.二叉树层序遍历-自底向上

自底向上,逐层从左向右遍历。
和从根节点开始遍历基本一样,只不过是在往结果里存储的时候顺序改变。

public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();if (root == null) {return levelOrder;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();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);}}// add(index, element)// 将元素添加到指定的索引处,原来的链表的索引向后移动// 每次都往索引0处放,达到后来的先放的效果levelOrder.add(0, level);}return levelOrder;
}

4.二叉树的锯齿形层序遍历

锯齿形层序遍历就是先从左往右遍历一层,再从右往左遍历一层。
和上面的算法基本一样,只不过要用一个布尔型的变量指示从左向右还是从右向左,从右向左的话就需要从链表的前边进行添加。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new LinkedList<List<Integer>>();if (root == null) {return ans;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);// 为true是从左向右遍历,为false是从右向左遍历boolean isOrderLeft = true;while (!queue.isEmpty()) {Deque<Integer> levelList = new LinkedList<Integer>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode curNode = queue.poll();if (isOrderLeft) {levelList.offerLast(curNode.val);} else {levelList.offFirst(curNode.val);}if (curNode.left != null) {queue.offer(curNode.left);}if (curNode.right != null) {queue.offer(curNode.right);}}ans.add(levelList);isOrderLeft = !isOrderLeft;}return ans;
}

5.N叉树的层序遍历

public List<List<Integer>> nLevelOrder(Node root) {List<List<Integer>> value = new ArrayList<>();Deque<Node> q = new ArrayDeque<>();if (root != null) {q.addLast(root);}while (!q.isEmpty()) {Deque<Node> next = new ArrayDeque<>();List<Integer> nd = new ArrayList<>();while (!q.isEmpty()) {Node cur = q.pollFirst();nd.add(cur.val);for (Node chd : cur.children) {if (chd != null) {next.add(chd);}}}q = next;value.add(nd);}return value;
}

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

用一个变量记录每行的最大值就好了。

public List<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> deque = new ArrayDeque<>();if (root != null) {deque.addLast(root);}while (!deque.isEmpty()) {int size = deque.size();int levelMaxNum = Integer.MIN_VALUE;for (int i = 0; i < size; i++) {TreeNode node = deque.poll();levelMaxNum = Math.max(node.val, levelMaxNum);if (node.left != null) {deque.addLast(node.left);}if (node.right != null) {deque.addLast(node.right);}}res.add(levelMaxNum);}return res;
}

7.在每个树行中找平均值

public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> list = new LinkedList<>();list.add(root);while (list.size() != 0) {int len = list.size();double sum = 0;for (int i = 0; i < len; i++) {TreeNode node = list.poll();sum += node.val;if (node.left != null) {list.add(node.left);}if (node.right != null) {list.add(node.right);}}res.add(sum/len);}return res;
}

8.二叉树的右视图

public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}if (i == size - 1) {res.add(node.val);}}}return res;
}

9.最底层最左边的值

回想锯齿形遍历时的isOrderLeft,这道题就是这个值一直取false,即从右向左遍历。那么就可以先添加右节点,再添加左节点,达到反过来的效果。

public int findBottomLeftValue(TreeNode root) {if (root.left == null && root.right == null) {return root.val;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);TreeNode temp = new TreeNode(0);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;
}

10.力扣404题

【持续更新】。

如果对您有帮助,请点赞关注支持我,谢谢!❤
如有错误或者不足之处,敬请指正!❤
个人主页:星不易 ♥
算法通关村专栏:不易|算法通关村 ♥

相关文章:

算法通关村第六关|白银|二叉树的层次遍历【持续更新】

1.二叉树基本的层序遍历 仅仅遍历并输出全部元素。 List<Integer> simpleLevelOrder(TreeNode root) {if (root null) {return new ArrayList<Integer>();}List<Integer> res new ArrayList<Integer>();LinkedList<TreeNode> queue new Lin…...

vue中通过js控制scss变量

<!--* Description:* Author: 李大玄* Date: 2022-07-28 20:34:43* FilePath: /web-framework-demo/src/views/layout.vue* LastEditors: 李大玄* LastEditTime: 2022-11-01 09:25:31 --> <template><div height"100%" class"b"><inp…...

深度学习理论知识入门【EM算法、VAE算法、GAN算法】和【RBM算法、MCMC算法、HMC算法】

目录 深度学习理论知识入门首先&#xff0c;让我们了解第一个流程&#xff1a;现在&#xff0c;让我们看看第二个流程&#xff1a; EM算法GMM&#xff08;高斯混合模型&#xff09; 深度学习理论知识入门 首先&#xff0c;让我们了解第一个流程&#xff1a; EM&#xff08;Exp…...

Java8实战-总结47

Java8实战-总结47 CompletableFuture&#xff1a;组合式异步编程让代码免受阻塞之苦使用定制的执行器 对多个异步任务进行流水线操作 CompletableFuture&#xff1a;组合式异步编程 让代码免受阻塞之苦 使用定制的执行器 就这个主题而言&#xff0c;明智的选择似乎是创建一个…...

功能: 在web应用程序中、读取文件

通过使用文件 API&#xff0c;web 内容可以要求用户选择本地文件&#xff0c;然后读取这些文件的内容。这种选择可以通过使用 HTML <input type"file"> 元素或通过拖放来完成。 1.通过 click() 方法使用隐藏的文件 input 元素 你可以隐藏公认难看的文件 <…...

TDD、BDD、ATDD以及SBE的概念和区别

在软件开发或是软件测试中会遇到以下这些词&#xff1a;TDD 、BDD 、ATDD以及SBE&#xff0c;这些词代表什么意思呢&#xff1f; 它们之间有什么关系吗&#xff1f; TDD 、BDD 、ATDD以及SBE的基本概念 TDD&#xff1a;&#xff08;Test Driven Development&#xff09;是一种…...

Android studio:打开应用程序闪退的问题

目录 问题描述分析原因解决方法 在开发Android应用程序的过程中遇到的问题 问题描述 在开发&#xff08;或者叫测试&#xff0c;这么简单的程序可能很难叫开发&#xff09;好一个android之后&#xff0c;在Android studio中调试开发好的app时&#xff0c;编辑器没有提示错误&a…...

Mysql数据库性能优化--performance_SCHEMA.STATEMENTS语句分析

使用performance_schema解决常见的故障案例 1 检查sql语句 使用performance_schema很容易找到引起性能问题的查询以及原因。 要启动语句检测&#xff0c;需要启动statement类型的插装。 插装类&#xff1a; statement/sql sql语句&#xff0c;如select,或者create table。s…...

[C/C++]数据结构 链表OJ题: 反转链表

描述: 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表 示例: 方法一: 让链表指向反向 如图所示: 代码思路: struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1NULL;struct ListNode* n2head;struct ListNode*…...

深度学习之基于YoloV5交通信号标志识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 基于YoloV5交通信号标志识别系统介绍 基于YoloV5的交通信号标志识别系统是一种深度学习应用&#xff0c;旨在通过使…...

Linux命令大全

荒诞也好&#xff0c;愚笨也好&#xff0c;总会过去的 文章目录 文件相关压缩相关tarzip 进程相关pskill 网络相关netstat IPC相关ipcsipcrm 系统资源相关topfreefdiskdfdu 权限相关umaskchmodchownchgrp 总结 文件相关 ls&#xff1a;列出当前目录中的文件和子目录。 ls常用…...

元宇宙是否为噱头?若不是,什么是元宇宙?他的概念、技术、应用和影响是什么?

文章来源&#xff1a;元宇宙的概念、技术、应用与影响——一项系统性文献综述 - 中国知网 (cnki.net) 摘要 [目的/意义]系统综述与分析当前国内外的元宇宙研究现状&#xff0c;有利于准确把握元宇宙发展方向&#xff0c;强化元宇宙基础研究&#xff0c;争取元宇宙建构权。[方法…...

293_C++_告警类

2、IncPos S32 AlarmList::IncPos(U32 *pu32Pos, U32 *pu32Cycle) {if((pu32Pos == NULL) || (pu32Cycle == NULL))</...

MySQL基础操作

注:mysql是大小写不敏感的. 1.数据库基础操作(展示) //1.展示当前数据库 show databases;//2.创建数据库 create database 数据库名;//3.使用数据库 use 数据库名;//4.删除数据库 drop database 数据库名;2.SQL中基本类型 2.1 数值类型(整数和浮点型) 注:decimal和numeric…...

ajax样式演示

以下是一段Ajax的演示代码&#xff0c;实现了通过Ajax获取后台数据并将其显示到前台页面上。 HTML文件: <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>Ajax演示</title></head><body><h1>学生…...

Web前端—CSS高级(定位、高级技巧、CSS修饰属性、综合案例:购物网站轮播图)

版本说明 当前版本号[20231108]。 版本修改说明20231107初版20231108对知识点&#xff08;圆点&#xff09;进行补充 目录 文章目录 版本说明目录day08-CSS高级01-定位相对定位绝对定位定位居中固定定位堆叠层级 z-index定位总结 02-高级技巧CSS精灵案例-京东服务HTML结构CS…...

linux的sftp复制传输文件

连接远程服务器 sftp -P 端口号 用户名主机 例如&#xff1a;sftp -P 80 ubuntu172.168.0.1 并按照提示输入密码 分别使用命令查看本地当前路径&#xff08;Local&#xff09; 和远程路径&#xff08;Remote&#xff09; pwd lpwd 使用 cd 远程路径和 lcd 本地路径分别进入对…...

【星海出品】flask(一)demo

如何安装很早就讲过了&#xff0c;这里就省略了 创建虚拟环境 python -m venv ./venv 激活虚拟环境 source venv/Scripts/activate 退出虚拟环境 deactivate 打开一个vue项目&#xff0c;安装一些东西&#xff0c;然后启动 npm run serve npm install element-plus --save npm…...

从vue源码中看diff算法

一、v-for必须要指定key&#xff0c;其作用是什么&#xff1f; 在源码中有一个函数为&#xff0c;其中就是通过判断两个vnode的type和key进行判断&#xff0c;如果这两个属性相同&#xff0c;那么这两个vnode就是相同&#xff0c;所以在设置key的时候也不可以设置为object等无…...

【17】c++11新特性 —>弱引用智能指针weak_ptr(2)

返回管理this的shared_ptr 通过wek_ptr返回管理this资源的共享智能指针对象shared_ptr。C11中为我们提供了一个模板类叫做std::enable_shared_from_this&#xff0c;这个类中有一个方法叫做shared_from_this()&#xff0c;通过这个方法可以返回一个共享智能指针&#xff0c;在…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...