二叉树的层序遍历,力扣
目录
题目地址:
题目:
我们直接看题解吧:
解题方法:
方法分析:
解题分析:
解题思路:
代码实现:
代码补充说明:
题目地址:
102. 二叉树的层序遍历 - 力扣(LeetCode)
难度:中等
今天刷二叉树的层序遍历,大家有兴趣可以点上看看题目要求,试着做一下。
题目:
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
我们直接看题解吧:
解题方法:
利用方法为广度优先遍历算法(BFS)
方法分析:
DFS(深度优先搜索)和 BFS(广度优先搜索)就像孪生兄弟,提到一个总是想起另一个。然而在实际使用中,我们用 DFS 的时候远远多于 BFS。那么,是不是 BFS 就没有什么用呢?
如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话,那么 DFS 和 BFS 的能力没什么差别,我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过,某些使用场景是 DFS 做不到的,只能使用 BFS 遍历。比如层序遍历、最短路径。
实际上,「BFS 遍历」、「层序遍历」、「最短路径」实际上是递进的关系。在 BFS 遍历的基础上区分遍历的每一层,就得到了层序遍历。在层序遍历的基础上记录层数,就得到了最短路径。
解题分析:
对于这道题,我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的层数 level 值都是父亲节点的层数 level 值加一。最后根据每个点的层数 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以层数 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。
但是考虑优化空间开销,不用哈希映射,并且只用一个变量 node 表示状态,因此可以利用队列实现这个功能
·首先根元素入队
·当队列不为空的时候
·求当前队列的长度 依次从队列中取si个元素进行拓展,然后进入下一次迭代
它和普通广度优先搜索的区别在于,普通广度优先搜索每次只取一个元素拓展,而这里每次取si个元素。
解题思路:
1、创建双端给队列queue放当前层的节点,创建二维数组res保存遍历所得的节点结果
2、进行初始化,在队列queue中添加root(若非空)
3、BFS循环,当队列queue空时结束循环
a.新建一个临时表tmp,用于存储当前层的打印结果
b.当前层打印循环: 循环次数为当前层节点数(即队列 queue 长度)。
·出队: 取队首节点,记为 node,。
·打印: 将节点值node.val 添加至 tmp 尾部。
· 更新queue: 若 node 的左(右)子节点不为空,则将左(右)子节点加入队列 queue 。即将当前层每个节点子节点放入queue
c.将当前层结果 tmp 添加入 res 。
4、返回值: 返回打印结果列表 res 即可。
代码实现:
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();//创建双端队列queueList<List<Integer>> res = new ArrayList<>();//创建二维列表resif (root != null) queue.add(root); //将root节点加到队列中while (!queue.isEmpty()) {//队列空时退出循环List<Integer> tmp = new ArrayList<>();//新建临时数组tmpfor(int i = queue.size(); i > 0; i--) {//当前层的循环遍历TreeNode node = queue.poll();//取出一个节点进行遍历tmp.add(node.val); //将节点值加到tmpif (node.left != null) queue.add(node.left);//非空则遍历该节点的左子树if (node.right != null) queue.add(node.right);//非空则遍历该节点的右子树}res.add(tmp);//当前层节点值加到res}return res;//返回树的遍历结果}
}
代码补充说明:
1、代码中实际上对树进行了非空的判断,若为空,则会返回空表res=[ ]
2、在当前层for循环中:
初始值是每个队列的长度(会发生变化),然后递减,
而这样做好处在于,下面我更新队列 queue的元素时,它不会影响我遍历当前层的的节点数,因为for循环初始化只执行一次
相关文章:

二叉树的层序遍历,力扣
目录 题目地址: 题目: 我们直接看题解吧: 解题方法: 方法分析: 解题分析: 解题思路: 代码实现: 代码补充说明: 题目地址: 102. 二叉树的层序遍历 - 力扣&…...
构建Dockerfile报错/bin/sh: 1: cd: can‘t cd to /xxx/yyy问题记录
目录 关键的命令行 排查分析 原因 附:Dockerfile构建时打印命令输出的办法 关键的命令行 WORKDIR /app COPY record . RUN cd record && xxx 执行到RUN时报了错: /bin/sh: 1: cd: cant cd to /app/record 并且宿主机当前目录也准备好了re…...

Vue常用的修饰符详解(有哪些,怎么用)
文章目录 一、修饰符是什么二、修饰符的作用1.表单修饰符lazytrimnumber 2.事件修饰符stoppreventselfoncecapturepassivenative 3.鼠标按钮修饰符4.键盘修饰符5.v-bind修饰符asyncpropscamel 三、应用场景参考文献 一、修饰符是什么 在程序世界里,修饰符是用于限定…...
Linux C/C++ 获取CPUID
实现方式: INTEL CC 格式 AT^T CC 格式 GCC/C库 __cpuid 宏 大致讲义: AT^T 格式汇编很反人类,GCC可以改编译器选项为INTEL内嵌汇编,但一般在GCC还是按照默认的AT^T汇编来拽写把,不想用也可以让AI工具把INTEL内嵌…...

2023年“中银杯”安徽省网络安全B模块(部分解析)
前言 以下是2023年中银杯安徽省网络安全B模块题目,镜像可以私聊我 B模块安全事件响应/网络安全数据取证/应用安全(400 分) B-1:CMS网站渗透测试 任务环境说明: √服务器场景:Server2206(关…...
194.【2023年华为OD机试真题(C卷)】单行道汽车通行时间(迭代计算—JavaPythonC++JS实现)
请到本专栏顶置查阅最新的华为OD机试宝典 点击跳转到本专栏-算法之翼:华为OD机试 🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,深度掌握! 文章目录 【2023年华为OD机试真题(C卷)】单行道汽车通行时间(…...

第二证券机构策略:股指预计维持蓄势震荡格局 关注煤炭、电力等板块
第二证券以为,技能面看,在元旦节前资金抄底推进指数收回2900整数关口,并向着3000点渠道压力前进。沪指在底部均线位支撑摆放较强,调整空间估计不大,在3000点渠道下方调整就是再次优化低吸的时机。操作上,在…...

Go 泛型之泛型约束
Go 泛型之泛型约束 文章目录 Go 泛型之泛型约束一、引入二、最宽松的约束:any三、支持比较操作的内置约束:comparable四、自定义约束五、类型集合(type set)六、简化版的约束形式七、约束的类型推断八、小结 一、引入 虽然泛型是…...

【数据仓库与联机分析处理】数据仓库
目录 一、数据仓库的概念 二、数据仓库与操作性数据库的区别 三、发展前期 四、数据仓库的系统结构 五、建模划分 六、主要案例 一、数据仓库的概念 目前很难给数据仓库(Data Warehouse)一个严格的定义,不准确地说,数据仓库…...

机器学习:贝叶斯估计在新闻分类任务中的应用
文章摘要 随着互联网的普及和发展,大量的新闻信息涌入我们的生活。然而,这些新闻信息的质量参差不齐,有些甚至包含虚假或误导性的内容。因此,对新闻进行有效的分类和筛选,以便用户能够快速获取真实、有价值的信息&…...

[C#]基于deskew算法实现图像文本倾斜校正
【算法介绍】 让我们开始讨论Deskeweing算法的一般概念。我们的主要目标是将旋转的图像分成文本块,并确定它们的角度。为了让您详细了解我将使用的方法: 照常-将图像转换为灰度。应用轻微的模糊以减少图像中的噪点。现在,我们的目标是找到带…...

Qt通过pos()获取坐标信息
背景:这是一个QWidget窗体,里面是各种布局的组合,一层套一层。 我希望得到绿色部分的坐标信息(x,y) QPoint get_pos(QWidget* w, QWidget* parent) {if ((QWidget*)w->parent() parent) {return w->pos();}else {QPoint pos(w->po…...
【Webpack】资源输入输出 - 配置资源出口
所有与出口相关的配置都集中在 output对象里 output对象里可以包含数十个配置项,这里介绍几个常用的 filename 顾名思义,filename的作用是控制输出资源的文件名,其形式为字符串,如: module.exports {entry: ./src/a…...

【XR806开发板试用】XR806串口驱动CM32M对小厨宝的控制实验
一.说明 非常感谢基于安谋科技STAR-MC1的全志XR806 Wi-FiBLE开源鸿蒙开发板试用活动,并获得开发板试用。 XR806是全志科技旗下子公司广州芯之联研发设计的一款支持WiFi和BLE的高集成度无线MCU芯片,支持OpenHarmony minisystem和FreeRTOS,具有集成度高、…...

中介者模式-Mediator Pattern-1
如果在一个系统中对象之间的联系呈现为网状结构, 对象之间存在大量的多对多联系,将导致系统非常复杂。 这些对象既会影响别的对象,也会被别的对象所影响。 这些对象称为同事对象,它们之间通过彼此的相互作用实现系统的行为。 在网…...

ASP.NET Core基础之图片文件(一)-WebApi图片文件上传到文件夹
阅读本文你的收获: 了解WebApi项目保存上传图片的三种方式学习在WebApi项目中如何上传图片到指定文件夹中 在ASP.NET Core基础之图片文件(一)-WebApi访问静态图片文章中,学习了如何获取WebApi中的静态图片,本文继续分享如何上传图片。 那么…...
精准掌控 Git 忽略规则:定制化 .gitignore 指南
🧙♂️ 诸位好,吾乃诸葛妙计,编程界之翘楚,代码之大师。算法如流水,逻辑如棋局。 📜 吾之笔记,内含诸般技术之秘诀。吾欲以此笔记,传授编程之道,助汝解技术难题。 &…...

Harmony 开始支持 Flutter ,聊聊 Harmony 和 Flutter 之间的因果
原创作者:恋猫de小郭 相信大家都已经听说过,明年的 Harmony Next 版本将正式剥离 AOSP 支持 ,基于这个话题我已经做过一期问题汇总 ,当时在 现有 App 如何兼容 Harmony Next 问题上提到过: 华为内部也主导适配目前的主…...

k8s 之7大CNI 网络插件
一、介绍 网络架构是Kubernetes中较为复杂、让很多用户头疼的方面之一。Kubernetes网络模型本身对某些特定的网络功能有一定要求,但在实现方面也具有一定的灵活性。因此,业界已有不少不同的网络方案,来满足特定的环境和要求。 CNI意为容器网络…...

stable diffusion 人物高级提示词(一)头部篇
一、女生发型 prompt描述推荐用法Long hair长发一定不要和 high ponytail 一同使用Short hair短发-Curly hair卷发-Straight hair直发-Ponytail马尾high ponytail 高马尾,一定不要和 long hair一起使用,会冲突Pigtails2条辫子-Braid辫子只写braid也会生…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...

如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...

Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...