二叉树——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…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
