二叉树——9.找树左下角的值
力扣题目链接
给定一个二叉树,在树的最后一行找到最左边的值。
示例:
输出:7
题干很简单,找到树的最后一行,在该行找到最左边的值,结合完整代码进行分析。
完整代码如下:
class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')self.result = Noneself.traversal(root, 0)return self.resultdef traversal(self, node, depth):if not node.left and not node.right:if depth > self.max_depth:self.max_depth = depthself.result = node.valreturnif node.left:depth += 1self.traversal(node.left, depth)depth -= 1if node.right:depth += 1self.traversal(node.right, depth)depth -= 1
首先初始化max_depth,用来记录当前访问到的最大深度。初始值设为负无穷大,保证第一次遇到叶子节点时会更新深度。初始化一个属性result,用来存储最底层最左边节点的值。调用辅助方法traversal,开始递归遍历二叉树,初始深度设为0。遍历完成后,返回最底层最左边节点的值。
接着开始定义辅助函数traversal。
if not node.left and not node.right:if depth > self.max_depth:self.max_depth = depthself.result = node.valreturn
检查当前节点是否是叶子节点(即没有左子节点和右子节点)。如果是叶子节点则进入下一层if,如果当前节点的深度大于已记录的最大深度,更新最大深度和结果值。更新max_depth为当前节点的深度,更新result为当前节点的值。
if node.left:depth += 1self.traversal(node.left, depth)depth -= 1if node.right:depth += 1self.traversal(node.right, depth)depth -= 1
如果当前节点有左子节点,递归遍历左子树。depth += 1是一个计数操作,将当前节点的深度增加1,这表示我们正在进入二叉树的下一层。在递归调用之前增加深度是为了确保递归调用时能够正确地反映该节点在二叉树中的实际深度。
接着,开始递归遍历左子树,传入左子节点和更新后的深度,一直递归调用,直到到达叶子节点(即没有子节点的节点)为止。depth -= 1是一个还原操作,将深度恢复到递归调用之前的状态。这是为了确保在处理完左子树后,能够正确地继续处理其他子树或返回到上一层节点。
右子树同理。
结合完整代码,题目思路为一层一层向下探索,直到找到叶子节点,更新深度和结果。返回上一层进入另一子树,继续递归,只要发现深度更低的叶子结点就更新之前的深度和结果,直到遍历完所有树。
但应该也有同学发现了,在该代码中更新深度的条件只有是叶子节点且if depth > self.max_depth,那如果最下层只有一个节点,且该节点为右叶子,那这个右叶子算这棵树的左下角的值吗?在该道题目中,按上述代码进行提交,结果是正确的,所以在该题目中如果最下层只有一个节点,且该节点为右叶子,那这个右叶子算这棵树的左下角的值。
方法二:队列迭代
from collections import dequeclass Solution:def findBottomLeftValue(self, root: TreeNode) -> int:queue = deque([root]) # 使用队列来进行广度优先搜索while queue:node = queue.popleft() # 弹出当前层的节点# 这里重要的是先把右节点入队,再把左节点入队if node.right:queue.append(node.right)if node.left:queue.append(node.left)# 最后弹出的 node 就是最后一层最左边的节点return node.val
首先,将根节点推入队列。只要队列中还有数就继续while循环,把根节点从队列中弹出赋值给node,如果当前node有右子树,先将右子节点推入队列,再将左子节点推入队列。先右后左,这是为了保证每一层先将右侧的节点弹出。结合示例进行分析:
1/ \2 3/ / \4 5 6\7
初始队列为[1],队列存在数进入while循环,弹出队列最左侧的数1作为node,1存在右子节点3,则当前队列为[3],1存在左节点2,则当前队列为[3,2]。队列存在,弹出队列最左侧节点3作为node,3存在右子节点,则当前队列为[2,6],3存在左子节点,则当前队列为[2,6,5]。队列存在,弹出最左侧节点2作为node,2只存在左子节点4,则当前队列为[6,5,4]。队列存在,弹出6作为node,6只存在右子节点7,则当前队列为[5,4,7],一个个弹出,最后弹出7为最后的值。将该代码提交,结果也同样正确,所以在该题目中如果最下层只有一个节点,且该节点为右叶子,那这个右叶子算这棵树的左下角的值。
相关文章:

二叉树——9.找树左下角的值
力扣题目链接 给定一个二叉树,在树的最后一行找到最左边的值。 示例: 输出:7 题干很简单,找到树的最后一行,在该行找到最左边的值,结合完整代码进行分析。 完整代码如下: class Solution:d…...
如何用github制作个人网站
这里整理了一些参考资料。总结来说,如果系统学过html网页制作的话,可以不用看这篇博客了;这里适合于小白,就是那种 没有做过网页、打算以别人优秀的个人主页为框架做网页的小白。 一、简单说明 这是利用github.io来制作网页的&a…...

二.PhotoKit - 相册权限(彻底读懂权限管理)
引言 用户的照片和视频算是用户最私密的数据之一,由于内置的隐私保护功能,APP只有在用户明确授权的前提下才能访问用户的照片库。从iOS14 开始,PhotoKit进一步增强了用户的隐私控制,用户可以选择指定的照片或者视频资源的访问权限…...

二叉树------最小堆,最大堆。
什么是最小堆: 堆是一种二叉树,最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。(节点左上角是编号,内部是元素值) 假设该图中的堆顶元素是24呢&a…...
预约功能的知识整理
前置知识 如果项目为小程序的开发项目中: 我们确定数据库中有的字段有: 预约人姓名、手机号、家人名称、预约时间 根据我们的经定一表必须要有的6个字段: 主键、创建时间、修改时间、创建人、修改人、备注 使用我们现在有的字段为: 主键…...

Linux的常用操作-02
一:Linux的系统目录结构 /bin bin是ary的缩写,这个目录存放着最经常用的命令 /boot:这里存放的是启动Linux时使用的一些核心文件,包括一些连接文件以及镜像文件。 /dev:dev是Device(设备)的缩写,该目录下存放的是Lin…...

Android Studio 连接手机进行调试
总所周知,Android Studio里的虚拟手机下载后又大又难用。不如直接连手机用。本篇文章主要内容为Android Studio怎么连接手机进行程序调试。 1. 在AndroidSDK中下载google USB Driver: 2. 连接手机: 进入电脑设备管理器界面。并点开便携设备,…...

Vue3项目创建及相关配置
Vue是一种用于构建用户界面的JavaScript框架。它采用了一种称为MVVM(Model-View-ViewModel)的架构模式。 MVVM是一种将用户界面与业务逻辑和数据分离的设计模式。它包括三个部分: Model(模型):表示应用程序…...
【Python】Python中一些有趣的用法
Python是一种非常灵活和强大的编程语言,它有很多有趣的用法,以下是一些例子: 一行代码实现FizzBuzz: print(\n.join([FizzBuzz[i%3*4:i%5*8:-1] or str(i) for i in range(1, 101)]))使用列表推导式生成斐波那契数列: …...

RCE复现问题和研究
目录 先了解一些常见的知识点 PHP常见命令执行函数 call_user_func eval() call_user_func_array array_filter 实战演练(RCE)PHP Eval函数参数限制在16个字符的情况下 ,如何拿到Webshell? 1、长度…...

MySQL中的索引——适合创建索引的情况
1.适合创建索引的情况 1、字段的数值有唯一性的限制 2、频繁作为 WHERE 查询条件的字段 某个字段在 SELECT 语句的 WHERE 条件中经常被使用到,那么就需要给这个字段创建索引了。尤其是在数据量大的情况下,创建普通索引就可以大幅提升数据查询的效率。 …...

5款在线伪原创改写软件,智能改写文章效果好
在这个信息爆炸的时代,内容创作变得愈发重要,而对于创作者来说,有时需要一些得力的伪原创改写工具来辅助我们更好地改写出高质量的内容。今天我要和大家分享5款令人惊喜的在线伪原创改写软件,它们以出色的智能改写效果,…...

opencv-python图像增强四:多曝光融合(方法一)
文章目录 一、简介:二、多曝光融合方案:三、算法实现步骤3.1 读取图像与曝光时间:3.2 计算响应曲线并合并3.3 色调映射 四:整体代码实现五:效果 一、简介: 在摄影和计算机视觉领域,高动态范围&…...

Qt 实战(9)窗体 | 9.2、QDialog
文章目录 一、QDialog1、基本概念2、常用特性2.1、模态与非模态2.2、数据交互 3、总结 前言: Qt框架中的QDialog类是一个功能强大且灵活的对话框控件,广泛应用于各种GUI(图形用户界面)应用程序中,用于处理用户输入、消…...
Spring 事务机制
1. 引言 1.1 什么是事务 事务是由用户定义的一系列操作序列所组成的最小工作单元;这些操作要么全部完成,要么全部不完成,是一个不可分割的工作单元。常见于数据库中的并发控制和数据一致性处理场景。 1.2 事务的特性 事务具有以下特性&am…...

Android 13 GMS 内置壁纸
如图,原生系统上,设备上的壁纸 显示系统内置壁纸。如果没有添加内置壁纸,就显示默认的壁纸。点击进去就是预览页面 扩展下,默认壁纸在 frameworks/base/core/res/res/drawable-sw720dp-nodpi/default_wallpaper.png frameworks/b…...
【LeetCode】234. 回文链表
回文链表 题目描述: 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 示例 1: 输入:head [1,2,2,1] 输出:true示例 2&#…...

零基础学会机器学习,到底要多久?
这两天啊,有不少朋友和我说,想学机器学习,但是之前没有基础,不知道能不能学得会。 首先说结论,只要坚持,就能学会,但是一定不能三天打鱼两天晒网,要持之以恒,至少每隔两…...

视频汇聚/安防监控综合平台EasyCVR接入海康私有协议EHOME显示失败是什么原因?
安防监控/视频综合管理平台/视频集中存储/磁盘阵列EasyCVR视频汇聚平台,支持多种视频格式和编码方式(H.264/H.265),能够轻松对接各类前端监控设备,实现视频流的统一接入与集中管理。安防监控EasyCVR平台支持多种流媒体…...
Qt解析XML
背景 本来想解析VS的项目配置文件(*.vcxproj),配合cppclean来发现多余的#incldue。 结果发现低估了难度,VS会间接引入许多目录。 略有不甘,暂且作为一个解析XML文件的示例。 代码 VSProjectParser.h #include <QVector> #include…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...