【LeetCode热题100】--102.二叉树的层序遍历
102.二叉树的层序遍历

广度优先搜索:
我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。
考虑如何优化空间开销:如何不用哈希映射,并且只用一个变量 node 表示状态,实现这个功能呢?
我们可以用一种巧妙的方法修改广度优先搜索:
- 首先根节点入队
- 当队列不为空时:
- 求当前队列的长度 s i s_i si
- 依次从队列中取 s i s_i si个元素进行拓展,然后进入下一次迭代
它和普通广度优先搜索的区别在于:普通广度优先搜索每次只取一个元素拓展,而这里每次取 s i s_i si个元素
/*** 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<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<List<Integer>>();if(root == null){return ans;} //队列是先进先出Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root); //队列中添加根节点while(!queue.isEmpty()){List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for(int i = 1;i<=currentLevelSize;i++){TreeNode node = queue.poll();level.add(node.val);//如果左节点不为空,队列中先添加左节点if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}ans.add(level);}return ans;}
}
相关文章:
【LeetCode热题100】--102.二叉树的层序遍历
102.二叉树的层序遍历 广度优先搜索: 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类&…...
第44节——redux store
一、概念 Redux 是一个用于管理 JavaScript 应用状态的库。在 Redux 中,整个应用的状态都存储在一个对象中,称为 store。 Store 实际上是一个 JavaScript 对象,它存储了整个应用的状态。它是唯一的,意味着应用中只有一个 store。…...
【2023年11月第四版教材】第17章《干系人管理》(第二部分)
第17章《干系人管理》(第二部分) 4 过程1-识别干系人4.1 数据收集★★★4.3数据分析4.4 权力利益方格4.5 数据表现:干系人映射分析和表现★★★ 5 过程2-规划干系人参与5.1 数据分析5.2 数据表现★★★5.2.1 干系人参与度评估矩阵★★★ 5.3 …...
含分布式电源的配电网可靠性评估(matlab代码)
目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 该程序参考《基于仿射最小路法的含分布式电源配电网可靠性分析》文献方法,通过概率模型和时序模型分别进行建模,实现基于概率模型最小路法的含分布式电源配电网可靠性评估以及时序模型…...
react的组件
组件 组件是用来实现局部功能的代码和资源的集合(html/css/js),用来复用代码。 react中分为函数式组件和类式组件。函数式组件就是一个函数,函数的返回值就是组件的视图内容。类式组件就是通过class关键字创建的类,类…...
低功耗引擎Cliptrix为什么可以成为IOT的高效能工具
在万物互联的时代,现代人已普遍接受电视、音箱等电器设备具备智能化能力,也是在这个趋势下,我们身边越来越多的iOT设备联网和交互成为刚需。 但iot设备也面临到一些非常显著的痛点,例如iot设备的内存、处理器等核心元件无法与手机…...
深入学习git
1、git原理及整体架构图 一些常用的命令 git add . 或 git add src/com/ygl/hello/hello.java 指定文件 git commit . 或 git commit src/com/ygl/hello/hello.java 指定文件 git push origin 分支名称 2、git stash的应用场景 场景一:你正在当前分支A开发&…...
第9章 Mybatis
9.1 谈谈你对Mybatis的理解 难度:★★ 重点:★★ 白话解析 说清楚Mybatis是什么,它的工作流程,然后再对比一下Hibernate就好了。 1、Mybatis是什么:它一个半自动ORM框架,它底层把JDBC那套加载驱动、创建连接、创建statement等重复性的硬编码全部给你封装好了,程序员只…...
隐蔽通信论文复现
文章目录 前言一、Limits of Reliable Communication with Low Probability of Detection on AWGN Channels摘要introduction 前言 本文准备先考虑隐蔽中通信经典的Alice, Bob, Willie三点模型, 总结出其中的经典套路 一、Limits of Reliable Communication with Low Probabil…...
《Vue.js+Spring Boot全栈开发实战》简介
大家好,我是老卫。 恰逢中秋国庆双节,不想出门看人山,惟愿宅家阅书海! 今天开箱的这本书是《Vue.jsSpring Boot全栈开发实战》。 外观 从书名故名思议,就是基于Vue.jsSpring Boot来实现企业级应用全栈开发。 该书由…...
机器人中的数值优化(二十)——函数的光滑化技巧
本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考,主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等,本系列文章篇数较多,不定期更新,上半部分介绍无约束优化,…...
搭建全连接网络进行分类(糖尿病为例)
拿来练手,大神请绕道。 1.网上的代码大多都写在一个函数里,但是其实很多好论文都是把网络,数据训练等分开写的。 2.分开写就是有一个需要注意的事情,就是要import 要用到的文件中的模型或者变量等。 3.全连接的回归也写了&#…...
【小沐学前端】Node.js实现基于Protobuf协议的UDP通信(UDP/TCP)
文章目录 1、简介1.1 node1.2 Protobuf 2、下载和安装2.1 node2.2 Protobuf2.2.1 安装2.2.2 工具 3、node 代码示例3.1 HTTP3.2 UDP单播3.4 UDP广播 4、Protobuf 代码示例4.1 例子: awesome.proto4.1.1 加载.proto文件方式4.1.2 加载.json文件方式4.1.3 加载.js文件方式 4.2 例…...
Verasity Tokenomics — 社区讨论总结与下一步计划
Verasity 代币经济学的社区讨论已结束。 本次讨论从 8 月 4 日持续到 9 月 29 日,是区块链领域规模最大的讨论之一,超过 500,000 名 VRA 持有者和社区成员参与讨论,并收到了数千份回复。 首先,我们要感谢所有参与讨论并提出详细建…...
JUC第十三讲:JUC锁: ReentrantLock详解
JUC第十三讲:JUC锁: ReentrantLock详解 本文是JUC第十三讲,JUC锁:ReentrantLock详解。可重入锁 ReentrantLock 的底层是通过 AbstractQueuedSynchronizer 实现,所以先要学习上一章节 AbstractQueuedSynchronizer 详解。 文章目录 …...
WSL2安装历程
WLS2安装 1、系统检查 安装WSL2必须运行 Windows 10 版本 2004 及更高版本(内部版本 19041 及更高版本)或 Windows 11。 查看 Windows 版本及内部版本号,选择 Win R,然后键入winver。 2、家庭版升级企业版 下载HEU_KMS_Activ…...
Ubuntu20配置Mysql常用操作
文章目录 版权声明ubuntu更换软件源Ubuntu设置静态ipUbuntu防火墙ubuntu安装ssh服务Ubuntu安装vmtoolsUbuntu安装mysql5.7Ubuntu安装mysql8.0Ubuntu卸载mysql 版权声明 本博客的内容基于我个人学习黑马程序员课程的学习笔记整理而成。我特此声明,所有版权属于黑马程…...
【解决方案】‘create’ is not a member of ‘cv::aruco::DetectorParameters’
‘create’ is not a member of ‘cv::aruco::DetectorParameters’ 在构建AruCo标定板标定位姿代码的过程中,发现代码中认为create并不是aruco::DetectorParameters的成员函数,这是因为在4.7.0及以上的OpenCV版本中,对ArUco的代码做调整&…...
门牌制作(蓝桥杯)
门牌制作 题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小蓝要为一条街的住户制作门牌号。 这条街一共有 2020 位住户,门牌号从 1 到 2020 编号。 小蓝制作门牌的方法是先制作 0 到 9 这几个数字字…...
支付宝支付模块开发
生成二维码 使用Hutool工具类生成二维码 引入对应的依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.7.5</version> </dependency><dependency><groupId>com.go…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
