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

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

102.二叉树的层序遍历

image-20231003084207712

广度优先搜索:

我们可以想到最朴素的方法是用一个二元组 (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.二叉树的层序遍历 广度优先搜索&#xff1a; 我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态&#xff0c;它表示某个节点和它所在的层数&#xff0c;每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类&…...

第44节——redux store

一、概念 Redux 是一个用于管理 JavaScript 应用状态的库。在 Redux 中&#xff0c;整个应用的状态都存储在一个对象中&#xff0c;称为 store。 Store 实际上是一个 JavaScript 对象&#xff0c;它存储了整个应用的状态。它是唯一的&#xff0c;意味着应用中只有一个 store。…...

【2023年11月第四版教材】第17章《干系人管理》(第二部分)

第17章《干系人管理》&#xff08;第二部分&#xff09; 4 过程1-识别干系人4.1 数据收集★★★4.3数据分析4.4 权力利益方格4.5 数据表现&#xff1a;干系人映射分析和表现★★★ 5 过程2-规划干系人参与5.1 数据分析5.2 数据表现★★★5.2.1 干系人参与度评估矩阵★★★ 5.3 …...

含分布式电源的配电网可靠性评估(matlab代码)

目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 该程序参考《基于仿射最小路法的含分布式电源配电网可靠性分析》文献方法&#xff0c;通过概率模型和时序模型分别进行建模&#xff0c;实现基于概率模型最小路法的含分布式电源配电网可靠性评估以及时序模型…...

react的组件

组件 组件是用来实现局部功能的代码和资源的集合&#xff08;html/css/js&#xff09;&#xff0c;用来复用代码。 react中分为函数式组件和类式组件。函数式组件就是一个函数&#xff0c;函数的返回值就是组件的视图内容。类式组件就是通过class关键字创建的类&#xff0c;类…...

低功耗引擎Cliptrix为什么可以成为IOT的高效能工具

在万物互联的时代&#xff0c;现代人已普遍接受电视、音箱等电器设备具备智能化能力&#xff0c;也是在这个趋势下&#xff0c;我们身边越来越多的iOT设备联网和交互成为刚需。 但iot设备也面临到一些非常显著的痛点&#xff0c;例如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的应用场景 场景一&#xff1a;你正在当前分支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全栈开发实战》简介

大家好&#xff0c;我是老卫。 恰逢中秋国庆双节&#xff0c;不想出门看人山&#xff0c;惟愿宅家阅书海&#xff01; 今天开箱的这本书是《Vue.jsSpring Boot全栈开发实战》。 外观 从书名故名思议&#xff0c;就是基于Vue.jsSpring Boot来实现企业级应用全栈开发。 该书由…...

机器人中的数值优化(二十)——函数的光滑化技巧

本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考&#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等&#xff0c;本系列文章篇数较多&#xff0c;不定期更新&#xff0c;上半部分介绍无约束优化&#xff0c;…...

搭建全连接网络进行分类(糖尿病为例)

拿来练手&#xff0c;大神请绕道。 1.网上的代码大多都写在一个函数里&#xff0c;但是其实很多好论文都是把网络&#xff0c;数据训练等分开写的。 2.分开写就是有一个需要注意的事情&#xff0c;就是要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 日&#xff0c;是区块链领域规模最大的讨论之一&#xff0c;超过 500,000 名 VRA 持有者和社区成员参与讨论&#xff0c;并收到了数千份回复。 首先&#xff0c;我们要感谢所有参与讨论并提出详细建…...

JUC第十三讲:JUC锁: ReentrantLock详解

JUC第十三讲&#xff1a;JUC锁: ReentrantLock详解 本文是JUC第十三讲&#xff0c;JUC锁&#xff1a;ReentrantLock详解。可重入锁 ReentrantLock 的底层是通过 AbstractQueuedSynchronizer 实现&#xff0c;所以先要学习上一章节 AbstractQueuedSynchronizer 详解。 文章目录 …...

WSL2安装历程

WLS2安装 1、系统检查 安装WSL2必须运行 Windows 10 版本 2004 及更高版本&#xff08;内部版本 19041 及更高版本&#xff09;或 Windows 11。 查看 Windows 版本及内部版本号&#xff0c;选择 Win R&#xff0c;然后键入winver。 2、家庭版升级企业版 下载HEU_KMS_Activ…...

Ubuntu20配置Mysql常用操作

文章目录 版权声明ubuntu更换软件源Ubuntu设置静态ipUbuntu防火墙ubuntu安装ssh服务Ubuntu安装vmtoolsUbuntu安装mysql5.7Ubuntu安装mysql8.0Ubuntu卸载mysql 版权声明 本博客的内容基于我个人学习黑马程序员课程的学习笔记整理而成。我特此声明&#xff0c;所有版权属于黑马程…...

【解决方案】‘create’ is not a member of ‘cv::aruco::DetectorParameters’

‘create’ is not a member of ‘cv::aruco::DetectorParameters’ 在构建AruCo标定板标定位姿代码的过程中&#xff0c;发现代码中认为create并不是aruco::DetectorParameters的成员函数&#xff0c;这是因为在4.7.0及以上的OpenCV版本中&#xff0c;对ArUco的代码做调整&…...

门牌制作(蓝桥杯)

门牌制作 题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 小蓝要为一条街的住户制作门牌号。 这条街一共有 2020 位住户&#xff0c;门牌号从 1 到 2020 编号。 小蓝制作门牌的方法是先制作 0 到 9 这几个数字字…...

支付宝支付模块开发

生成二维码 使用Hutool工具类生成二维码 引入对应的依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.7.5</version> </dependency><dependency><groupId>com.go…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...