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

二叉树的层序遍历,力扣

目录

题目地址:

题目:

我们直接看题解吧:

解题方法:

方法分析:

解题分析:

解题思路:

代码实现:

代码补充说明:


题目地址:

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循环初始化只执行一次

相关文章:

二叉树的层序遍历,力扣

目录 题目地址&#xff1a; 题目&#xff1a; 我们直接看题解吧&#xff1a; 解题方法&#xff1a; 方法分析&#xff1a; 解题分析&#xff1a; 解题思路&#xff1a; 代码实现&#xff1a; 代码补充说明&#xff1a; 题目地址&#xff1a; 102. 二叉树的层序遍历 - 力扣&…...

构建Dockerfile报错/bin/sh: 1: cd: can‘t cd to /xxx/yyy问题记录

目录 关键的命令行 排查分析 原因 附&#xff1a;Dockerfile构建时打印命令输出的办法 关键的命令行 WORKDIR /app COPY record . RUN cd record && xxx 执行到RUN时报了错&#xff1a; /bin/sh: 1: cd: cant cd to /app/record 并且宿主机当前目录也准备好了re…...

Vue常用的修饰符详解(有哪些,怎么用)

文章目录 一、修饰符是什么二、修饰符的作用1.表单修饰符lazytrimnumber 2.事件修饰符stoppreventselfoncecapturepassivenative 3.鼠标按钮修饰符4.键盘修饰符5.v-bind修饰符asyncpropscamel 三、应用场景参考文献 一、修饰符是什么 在程序世界里&#xff0c;修饰符是用于限定…...

Linux C/C++ 获取CPUID

实现方式&#xff1a; INTEL CC 格式 AT^T CC 格式 GCC/C库 __cpuid 宏 大致讲义&#xff1a; AT^T 格式汇编很反人类&#xff0c;GCC可以改编译器选项为INTEL内嵌汇编&#xff0c;但一般在GCC还是按照默认的AT^T汇编来拽写把&#xff0c;不想用也可以让AI工具把INTEL内嵌…...

2023年“中银杯”安徽省网络安全B模块(部分解析)

前言 以下是2023年中银杯安徽省网络安全B模块题目&#xff0c;镜像可以私聊我 B模块安全事件响应/网络安全数据取证/应用安全&#xff08;400 分&#xff09; B-1&#xff1a;CMS网站渗透测试 任务环境说明&#xff1a; √服务器场景&#xff1a;Server2206&#xff08;关…...

194.【2023年华为OD机试真题(C卷)】单行道汽车通行时间(迭代计算—JavaPythonC++JS实现)

请到本专栏顶置查阅最新的华为OD机试宝典 点击跳转到本专栏-算法之翼:华为OD机试 🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,深度掌握! 文章目录 【2023年华为OD机试真题(C卷)】单行道汽车通行时间(…...

第二证券机构策略:股指预计维持蓄势震荡格局 关注煤炭、电力等板块

第二证券以为&#xff0c;技能面看&#xff0c;在元旦节前资金抄底推进指数收回2900整数关口&#xff0c;并向着3000点渠道压力前进。沪指在底部均线位支撑摆放较强&#xff0c;调整空间估计不大&#xff0c;在3000点渠道下方调整就是再次优化低吸的时机。操作上&#xff0c;在…...

Go 泛型之泛型约束

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

【数据仓库与联机分析处理】数据仓库

目录 一、数据仓库的概念 二、数据仓库与操作性数据库的区别 三、发展前期 四、数据仓库的系统结构 五、建模划分 六、主要案例 一、数据仓库的概念 目前很难给数据仓库&#xff08;Data Warehouse&#xff09;一个严格的定义&#xff0c;不准确地说&#xff0c;数据仓库…...

机器学习:贝叶斯估计在新闻分类任务中的应用

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

[C#]基于deskew算法实现图像文本倾斜校正

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

Qt通过pos()获取坐标信息

背景&#xff1a;这是一个QWidget窗体&#xff0c;里面是各种布局的组合&#xff0c;一层套一层。 我希望得到绿色部分的坐标信息(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对象里可以包含数十个配置项&#xff0c;这里介绍几个常用的 filename 顾名思义&#xff0c;filename的作用是控制输出资源的文件名&#xff0c;其形式为字符串&#xff0c;如&#xff1a; module.exports {entry: ./src/a…...

【XR806开发板试用】XR806串口驱动CM32M对小厨宝的控制实验

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

中介者模式-Mediator Pattern-1

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

ASP.NET Core基础之图片文件(一)-WebApi图片文件上传到文件夹

阅读本文你的收获&#xff1a; 了解WebApi项目保存上传图片的三种方式学习在WebApi项目中如何上传图片到指定文件夹中 在ASP.NET Core基础之图片文件(一)-WebApi访问静态图片文章中&#xff0c;学习了如何获取WebApi中的静态图片&#xff0c;本文继续分享如何上传图片。 那么…...

精准掌控 Git 忽略规则:定制化 .gitignore 指南

&#x1f9d9;‍♂️ 诸位好&#xff0c;吾乃诸葛妙计&#xff0c;编程界之翘楚&#xff0c;代码之大师。算法如流水&#xff0c;逻辑如棋局。 &#x1f4dc; 吾之笔记&#xff0c;内含诸般技术之秘诀。吾欲以此笔记&#xff0c;传授编程之道&#xff0c;助汝解技术难题。 &…...

Harmony 开始支持 Flutter ,聊聊 Harmony 和 Flutter 之间的因果

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

k8s 之7大CNI 网络插件

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

stable diffusion 人物高级提示词(一)头部篇

一、女生发型 prompt描述推荐用法Long hair长发一定不要和 high ponytail 一同使用Short hair短发-Curly hair卷发-Straight hair直发-Ponytail马尾high ponytail 高马尾&#xff0c;一定不要和 long hair一起使用&#xff0c;会冲突Pigtails2条辫子-Braid辫子只写braid也会生…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

HTML 列表、表格、表单

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

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [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 解决&#xff1a; 不要动CMakeLists.…...

如何应对敏捷转型中的团队阻力

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

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

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

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...