二叉树的层序遍历,力扣
目录
题目地址:
题目:
我们直接看题解吧:
解题方法:
方法分析:
解题分析:
解题思路:
代码实现:
代码补充说明:
题目地址:
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也会生…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...

认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...

【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...