二叉树的层序遍历,力扣
目录
题目地址:
题目:
我们直接看题解吧:
解题方法:
方法分析:
解题分析:
解题思路:
代码实现:
代码补充说明:
题目地址:
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也会生…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
