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

代码随想录第17天:二叉树

一、二叉搜索树的最近公共祖先(Leetcode 235)

由于是二叉搜索树,节点的值有严格的顺序关系:左子树的节点值都小于父节点,右子树的节点值都大于父节点。利用这一点,可以在树中更高效地找到最低公共祖先。

class Solution:def traversal(self, cur, p, q):# 递归的基本情况:当前节点为空,返回 Noneif cur is None:return cur# 如果当前节点的值大于 p 和 q 的值,说明 p 和 q 都在左子树中if cur.val > p.val and cur.val > q.val:  # 左left = self.traversal(cur.left, p, q)  # 在左子树中递归查找if left is not None:return left  # 如果左子树中找到了节点,返回该节点# 如果当前节点的值小于 p 和 q 的值,说明 p 和 q 都在右子树中if cur.val < p.val and cur.val < q.val:  # 右right = self.traversal(cur.right, p, q)  # 在右子树中递归查找if right is not None:return right  # 如果右子树中找到了节点,返回该节点# 如果左右子树都不为空,说明 p 和 q 分别在左右子树中return cur  # 返回当前节点,因为当前节点就是它们的最低公共祖先def lowestCommonAncestor(self, root, p, q):return self.traversal(root, p, q)  # 从根节点开始查找 p 和 q 的最低公共祖先

二、二叉搜索树中的插入操作(Leetcode 701)

如果要插入的值小于当前节点的值,应该插入到左子树;如果要插入的值大于当前节点的值,应该插入到右子树。

class Solution:# 插入值 val 到二叉搜索树中def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 如果当前节点为空,创建一个新的节点并返回if root is None or root.val == val:return TreeNode(val)  # 创建一个新的 TreeNode 节点,包含插入的值# 如果当前节点值大于 val,则应该将 val 插入到左子树elif root.val > val:# 如果左子树为空,直接插入该值作为左子节点if root.left is None:root.left = TreeNode(val)  # 创建一个新的节点,并赋值给左子节点else:# 如果左子树不为空,递归地在左子树中插入 valself.insertIntoBST(root.left, val)# 如果当前节点值小于 val,则应该将 val 插入到右子树elif root.val < val:# 如果右子树为空,直接插入该值作为右子节点if root.right is None:root.right = TreeNode(val)  # 创建一个新的节点,并赋值给右子节点else:# 如果右子树不为空,递归地在右子树中插入 valself.insertIntoBST(root.right, val)# 返回根节点,确保树的结构未被破坏return root

三、删除二叉搜索树中的节点(Leetcode 450)

删除节点的三种情况:

1、节点没有子节点(叶子节点):如果节点没有左子树也没有右子树(即叶子节点),直接删除该节点,返回 None,表示当前节点被删除。

2、节点只有右子树:如果节点没有左子树(root.left is None),那么可以用右子树代替当前节点。删除该节点并返回右子节点,实际上是把右子树提升为当前节点的子树。

3、节点只有左子树:如果节点没有右子树(root.right is None),那么可以用左子树代替当前节点。删除该节点并返回左子节点,实际上是把左子树提升为当前节点的子树。

4、节点有两个子树:从当前节点的右子树开始,递归找到右子树中最左的节点(cur.left is None),该节点就是右子树中的最小节点。将该最小节点的左子树指向当前节点的左子树。

返回右子树作为新树的根节点(也就是当前节点被删除,右子树的最小节点替代了它的位置)。

class Solution:# 删除二叉搜索树中的节点def deleteNode(self, root, key):# 如果当前节点为空,返回空# 表示没有找到节点或到达树的末端if root is None:return root# 如果当前节点的值等于要删除的值if root.val == key:# 如果节点没有子节点(叶子节点),直接删除该节点if root.left is None and root.right is None:return None# 如果节点只有右子树,直接返回右子树,删除当前节点elif root.left is None:return root.right# 如果节点只有左子树,直接返回左子树,删除当前节点elif root.right is None:return root.left# 如果节点有两个子树,找到右子树中的最小节点(左子树的最左节点)else:cur = root.right  # 从右子树开始# 寻找右子树中最小的节点(左子树最深的节点)while cur.left is not None:cur = cur.left# 将右子树最小节点的左子树指向当前节点的左子树cur.left = root.left# 返回右子树作为新的根节点,替代当前节点return root.right# 如果当前节点的值大于要删除的值,递归到左子树中删除if root.val > key:root.left = self.deleteNode(root.left, key)# 如果当前节点的值小于要删除的值,递归到右子树中删除if root.val < key:root.right = self.deleteNode(root.right, key)# 返回根节点,确保树的结构未被破坏return root

相关文章:

代码随想录第17天:二叉树

一、二叉搜索树的最近公共祖先&#xff08;Leetcode 235&#xff09; 由于是二叉搜索树&#xff0c;节点的值有严格的顺序关系&#xff1a;左子树的节点值都小于父节点&#xff0c;右子树的节点值都大于父节点。利用这一点&#xff0c;可以在树中更高效地找到最低公共祖先。 c…...

第8篇:Linux程序访问控制FPGA端HEX<一>

Q&#xff1a;如何从DE1-SoC_Computer系统的ARM A9处理器访问FPGA端的七段数码管呢&#xff1f; A&#xff1a;DE1-SoC_Computer系统中有2个连接FPGA端HEX外设的并行端口HEX5_HEX4和HEX3_HEX0&#xff0c;每个端口有一个32位只读Data寄存器。地址为0xFF200020的寄存器驱动4个数…...

Android 添加一个自己的系统服务SystemService

Android 系统服务&#xff08;System Services&#xff09;是 Android 操作系统的核心组件&#xff0c;运行在系统层面&#xff0c;为应用程序提供底层硬件访问、系统资源管理以及跨应用功能支持。这些服务在后台持续运行&#xff0c;由系统进程&#xff08;如 system_server&a…...

git安装(windows)

通过网盘分享的文件&#xff1a;资料(1) 链接: https://pan.baidu.com/s/1MAenYzcQ436MlKbIYQidoQ 提取码: evu6 点击next 可修改安装路径 默认就行 一般从命令行调用&#xff0c;所以不用创建。 用vscode&#xff0c;所以这么选择。...

C# visionpro联合编程中遇到的问题之 R6025 - pure virtual function call

C# visionpro联合编程中遇到的问题之 R6025 - pure virtual function call R6025 pure virtual function call解决方法步骤 1: 获取所有相机步骤 2: 遍历并关闭相机完整代码 R6025 pure virtual function call 如果错误 “R6025 - pure virtual function call” 发生在关闭窗体…...

OTA技术(一):原理与实现方案

目录 一.引言 二.核心原理 2.1 定义与分类 2.2 系统架构 2.3 典型的升级流程 三.嵌入式系统中的OTA实现方案 3.1 存储空间划分 3.2 关键技术 一.引言 在智能手机上点击系统更新、电动汽车解锁新功能、智能家居设备自动修复漏洞……这些场景背后都离不开一项关键技术——…...

strings.LastIndexAny 使用详解

目录 1. 官方包 2. 支持版本 3. 官方说明 4. 作用 5. 实现原理 6. 推荐使用场景和不推荐使用场景 推荐场景 不推荐场景 7. 使用场景示例 示例1&#xff1a;官方示例 示例2&#xff1a;日志清洗&#xff08;去除末尾的乱码或非法字符&#xff09; 8. 性能对比 性能…...

大型商场运营新变革:AcrelCloud - 3200 预付费系统应用全解析

一、方案概述 在现代商业运营和物业管理中&#xff0c;大型商场、商业小区以及大集团和大物业面临着复杂的费用收取和管理难题。安科瑞的 AcrelCloud - 3200 远程预付费管控云平台&#xff0c;借助先进的预付费电表等设备&#xff0c;为解决这些问题提供了高效的一体化解决方案…...

鸿蒙开发07-interface

在 ArkTS&#xff08;HarmonyOS Ability Runtime TypeScript&#xff09;中&#xff0c;interface&#xff08;接口&#xff09;是一种强大的类型工具&#xff0c;它主要用于定义对象的结构&#xff0c;为对象的属性和方法提供类型约束&#xff0c;帮助开发者编写更加规范、可维…...

Java从入门到“放弃”(精通)之旅——方法的使用⑤

Java从入门到“放弃”&#xff08;精通&#xff09;之旅&#x1f680;——方法的使用⑤ &#x1f4d6;引言&#xff1a; 在编程领域&#xff0c;代码如同精密的齿轮相互咬合驱动程序运转。随着项目规模渐长&#xff0c;重复的代码片段如同冗余的齿轮&#xff0c;不仅增加负重…...

5 C 程序全流程解析:编写、预处理、编译、汇编、链接、运行与 GCC 指令详解

1 C 程序运行机制流程概述 通过以上步骤&#xff0c;我们可以将一个 C 语言源代码文件逐步转换为一个可执行的二进制程序。这一过程涉及多个关键工具和步骤&#xff0c;每一步都承担着特定的任务&#xff0c;发挥着独特的作用。深入理解这些步骤&#xff0c;不仅有助于我们更好…...

leetcode:1351. 统计有序矩阵中的负数(python3解法)

难度&#xff1a;简单 给你一个 m * n 的矩阵 grid&#xff0c;矩阵中的元素无论是按行还是按列&#xff0c;都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。 示例 1&#xff1a; 输入&#xff1a;grid [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 输…...

hive数仓要点总结

1.OLTP和OLAP区别 OLTP&#xff08;On-Line Transaction Processing&#xff09;即联机事务处理&#xff0c;也称为面向交易的处理过程&#xff0c;其基本特征是前台接收的用户数据可以立即传送到计算中心进行处理&#xff0c;并在很短的时间内给出处理结果&#xff0c;是对用…...

LeetCode[541]反转字符串Ⅱ

思路&#xff1a; 题目给我们加了几个规则&#xff0c;剩余长度小于2k&#xff0c;大于等于k就反转k个&#xff0c;小于k就全部反转&#xff0c;我们按照这个逻辑来就行。 第一就是大于等于k就反转k个&#xff0c;我们for循环肯定是i2k了&#xff0c;接下来就是判断是否大于等于…...

瑞幸微RK系列平台的YOLO部署(上篇)

&#x1f387;环境配置 &#x1f389;前言 部署的第一步是对环境的配置&#xff0c;不同的平台的平台需要依赖的环境不同&#xff0c;之前在英伟达的Jetson系列部署过&#xff0c;其主要是需要配置CUDA和CUDNN的环境&#xff0c;需要加速推理的话可能还需要TensorRT的环境。 …...

HarmonyOS:页面滚动时标题悬浮、背景渐变

一、需求场景 进入到app首页或者分页列表首页时&#xff0c;随着页面滚动&#xff0c;分类tab要求固定悬浮在顶部。进入到app首页、者分页列表首页、商品详情页时&#xff0c;页面滚动时&#xff0c;顶部导航栏&#xff08;菜单、标题&#xff09;背景渐变。 二、相关技术知识点…...

无人设备遥控器之安全防护与预警篇

无人设备遥控器的安全防护与预警是保障无人机、无人船、无人车等无人系统安全运行的关键环节。随着无人设备在农业、测绘、物流、安防等领域的广泛应用&#xff0c;其遥控器的安全性与可靠性显得尤为重要。 一、安全防护 1. 物理安全防护 外壳防护&#xff1a;采用防水、防尘…...

win10win11启用组策略编辑器

今天发现家庭版的win11系统没有组策略编辑器&#xff0c; 桌面新建txt文件&#xff0c;打开 编写以下脚本&#xff1a; echo off pushd "%~dp0" dir /b %SystemRoot%\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum >Li…...

谷歌浏览器的开发者模式如何开启及安装教程

在谷歌浏览器&#xff08;Google Chrome&#xff09;中开启开发者模式并安装扩展程序&#xff08;如未上架商店的插件或自定义扩展&#xff09;的步骤如下&#xff1a; 一、开启开发者模式 打开扩展管理页面 在浏览器地址栏输入&#xff1a;chrome://extensions/ 或通过菜单进入…...

WebRTC实时通话EasyRTC嵌入式音视频通信SDK,构建智慧医疗远程会诊高效方案

一、方案背景 当前医疗领域&#xff0c;医疗资源分布不均问题尤为突出&#xff0c;大城市和发达地区优质医疗资源集中&#xff0c;偏远地区医疗设施陈旧、人才稀缺&#xff0c;患者难以获得高质量的医疗服务&#xff0c;制约医疗事业均衡发展。 EasyRTC技术基于WebRTC等先进技…...

C++性能优化实战:从瓶颈定位到高并发架构重构(第一章)

在高并发编程的世界中,性能瓶颈往往潜伏在代码的深处,悄无声息地吞噬着系统的吞吐量。想象一下,你正在开发一个游戏服务器,需要在每毫秒内为数千名玩家分配和释放内存,任何微小的延迟都可能导致玩家体验的崩塌。你是否曾遇到过这样的困惑:增加了线程数,期待性能翻倍,结…...

Terraform 迷思:当优雅的模块 terraform-aws-eks 与现实碰撞

大家好&#xff0c;今天想和大家聊聊一个可能很多技术人都经历过的场景——面对看似完美的工具或代码库&#xff0c;却陷入意想不到的困境&#xff0c;甚至开始有点怀疑人生的时刻。 启程&#xff1a;雄心勃勃的 EKS 模块优化 故事的开端往往充满希望。就像我今天&#xff0…...

路由器端口映射的意思、使用场景、及内网ip让公网访问常见问题和解决方法

一、端口映射是什么意思 端口映射是将内网主机的IP地址端口映射到公网中&#xff0c;内部机器提供相应的互联网服务。当异地用户访问该这个端口时&#xff0c;会自动将请求映射到对应局域网内部的机器上。 二、端口映射常见使用场景 1&#xff0c;远程访问需求。当有…...

【MySQL 数据库】增删查改操作CRUD(下)

&#x1f525;博客主页&#x1f525;&#xff1a;【 坊钰_CSDN博客 】 欢迎各位点赞&#x1f44d;评论✍收藏⭐ 目录 1. 聚合函数 1.1 常见聚合函数 1.1.1 COUNT 1.1.2 SUM 1.1.3 AVG 1.1.4 MAX 2. Group by 分组 2.1 分组示例 3. having 语句 3.1 having 过滤结果 3…...

Android 日志输出模块

Android 日志输出模块 本文主要记录下封装的日志输出模块. 1: 主要功能 日志模块初始化,并设置日志级别支持将日志写入文件日志文件单个限制200M,按天记录到指定文件,文件达到阈值后,记录新的日志文件.支持导出日志文件zip. 2: 具体实现 日志整体初始化使用静态内部类的方式…...

群辉搭建静态网站

写在前面&#xff0c;本文章主要是记录自己搭建过程以备后来需要时温习下&#xff01; 1.安装并打开web station 2. 2.打开 File Station 找到web文件夹 把静态导航网站的代码下载下来&#xff0c;并上传到上面 web 文件夹下 3. 在Web Station 套件里面&#xff0c;在网页服…...

51单片机波特率与溢出率的关系

1. 波特率与溢出率的基本关系 波特率(Baud Rate)表示串口通信中每秒传输的位数(bps),而溢出率是定时器每秒溢出的次数。在51单片机中,波特率通常通过定时器的溢出率来生成。 公式关系: 波特率=溢出率/​分频系数 其中,分频系数与定时器的工作模…...

数据库原理及应用mysql版陈业斌实验三

&#x1f3dd;️专栏&#xff1a;Mysql_猫咪-9527的博客-CSDN博客 &#x1f305;主页&#xff1a;猫咪-9527-CSDN博客 “欲穷千里目&#xff0c;更上一层楼。会当凌绝顶&#xff0c;一览众山小。” 目录 实验三多表查询 1.实验数据如下 student 表&#xff08;学生表&#…...

Python 二分查找(bisect):排序数据的高效检索

二分查找&#xff1a;排序数据的高效检索 第二天清晨&#xff0c;李明早早来到了图书馆。今天他的研究目标是bisect模块&#xff0c;特别是其中的bisect_left和bisect_right函数。这些函数实现了二分查找算法&#xff0c;用于在已排序的序列中高效地查找元素或确定插入位置。 …...

ClickHouse

ClickHouse说明 ClickHouse是一种高性能、分布式的开源列式数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;专门用于在线分析处理&#xff08;OLAP&#xff09;工作负载。是俄罗斯的 Yandex 公司于 2016 年开源的列式存储数据库&#xff0c;使用 C 语言编写。ClickHou…...

【Linux生成SSH秘钥实现远程连接】Linux生成SSH秘钥对与修改服务配置文件实现无密码远程连接

文章目录 前言1. Linux 生成SSH秘钥对2. 修改SSH服务配置文件3. 客户端秘钥文件设置4. 本地SSH私钥连接测试5. Linux安装Cpolar工具6. 配置SSHTCP公网地址7. 远程SSH私钥连接测试8. 固定SSH公网地址9. 固定SSH地址测试 前言 在数字化江湖中&#xff0c;企业对各种技术的需求就…...

中间件--ClickHouse-4--向量化执行(什么是向量?为什么向量化执行的更快?)

1、向量&#xff08;Vector&#xff09;的概念 &#xff08;1&#xff09;、向量的定义 向量&#xff1a;在计算机科学中&#xff0c;向量是一组同类型数据的有序集合&#xff0c;例如一个包含多个数值的数组。在数据库中&#xff0c;向量通常指批量数据&#xff08;如一列数…...

conda导出环境以及安装环境

1. 导出环境 1.1导出完整的环境配置&#xff08;包含精确版本和平台信息&#xff09;&#xff1a; conda env export > /path/to/your/directory/environment.yml1.2 导出不含平台信息的配置&#xff08;更适合跨平台共享&#xff09;&#xff1a; conda env export --no…...

Mysql数据库基本操作-DML

有基础的可以直接看总结里面的思维导图 简单来说就是增删改 一、Mysql数据库基本操作-DML-insert-数据插入 如果写上列和值&#xff0c;那么相应的列要对应相应的值&#xff0c;而且列的类型要和值的类型相同 格式1&#xff1a;insert into 表&#xff08;列名&#xff09; v…...

html:文件上传-一次性可上传多个文件,将文件展示到页面(可删除

一、原始上传样式 1、效果 2、完整代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" cont…...

计算机网络(第四章)

网络层 一、网络层提供的两种服务 虚电路 &#xff1a;虚电路是一种在通信开始之前建立连接的方式。它类似于电话通话&#xff0c;双方在通话前要建立连接&#xff1b;数据报 &#xff1a;数据报是一种无连接的通信方式。每个数据包&#xff08;数据报&#xff09;独立地发送…...

【PostgreSQL教程】PostgreSQL 特别篇之 语言接口连接PHP

博主介绍:✌全网粉丝22W+,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物联网、机器学习等设计与开发。 感兴趣的可…...

Java学习——day30(Lambda表达式与 StreamAPI)

文章目录 1. Lambda 表达式1.1 概述1.2 应用场景1.3 示例代码 2. Stream API2.1 概述2.2 基本组成2.3 示例代码 3.练习3.1 .练习初级&#xff1a;3.2 中级&#xff1a;3.3 高级&#xff1a; 4.总结与应用4.1 Lambda 表达式4.2 Stream API 1. Lambda 表达式 1.1 概述 定义&…...

mysql no space left on device

文章目录 1. 查看磁盘使用情况2. 清理 /tmp 目录3. 调整 MySQL 临时文件目录4. 增加磁盘空间5. 优化数据库操作 我在执行 MySQL 的 UPDATE 语句时遇到 error writing file /tmp/*** no space left on device 错误&#xff0c;这表明 MySQL 临时文件存储目录 /tmp 空间不足。以下…...

异步编程——微信小程序

1. 前言 引用来自&#xff1a;微信小程序开发中的多线程处理与异步编程_微信小程序 多线程-CSDN博客 微信小程序是基于JavaScript开发的&#xff0c;与浏览器JavaScript不同&#xff0c;小程序运行在WebView内部&#xff0c;没有多线程的概念。小程序的 JavaScript 是单线程的…...

聊透多线程编程-线程池-8.C# 线程互斥实现方式

目录 1. 锁机制 (Locking Mechanisms) (1) lock 关键字 (2) Monitor 类 2. 跨进程互斥机制 3. 信号量机制 (1) Semaphore 和 SemaphoreSlim 4. 读写锁机制 (1) ReaderWriterLockSlim 5. 原子操作机制 (1) Interlocked 类 6. 自旋锁机制 (1) SpinLock 线程互斥是一种…...

渗透测试学习-概述

1.渗透测试 渗透测试( Penetration Testing &#xff09;是指受信任的第三方通过模拟黑客的攻击技术与手段对目标网络、系统进行攻击测试&#xff0c;发现目标的安全隐患并给出安全加固建议的一种安全测试与评估方法。 具体来讲&#xff0c;渗透人员在不同的位置&#xff08;…...

一键解锁Landsat 9地表温度计算!ENVI与ArcGIS Pro全流程详解(无需NASA大气校正)

为什么选择Landsat 9的L2SP数据&#xff1f; 之前&#xff1a;《ArcGIS与ENVI——基于landsat与Modis影像的遥感技术的生态环境质量评价》&#xff0c;基于Landsat前期的产品计算温度反演数据需要一系列复杂的步骤。 现在&#xff1a; Landsat 8-9的Collection 2 Level-2&…...

线代第七课:范德蒙德压缩

比如&#xff1a; 解析&#xff1a; 观看笔记来源&#xff1a; 《线性代数》教学视频 宋浩老师&#xff08;2024年更新&#xff09;...

Spark-SQL(一)

Spark SQL 概述 Spark SQL是Apache Spark用于处理结构化数据的模块 特点 1 易整合。无缝的整合了 SQL 查询和 Spark 编程 2 统一的数据访问。使用相同的方式连接不同的数据源 3 兼容 Hive。在已有的仓库上直接运行 SQL 或者 HQL 4 标准数据连接。通过 JDBC 或者 ODBC 来连…...

(自用)window防火墙关闭

自己老师忘了怎么关防火墙&#xff0c;导致每次都要重新找一遍&#xff0c;再下软件&#xff0c;所以写这篇 把这个地方打开可以看到被隔离的软件&#xff0c;然后点击还原即可使用了...

楼宇自控为建筑带来生机,具体表现在哪些方面?

在现代建筑领域&#xff0c;楼宇自控系统宛如一股清新的春风&#xff0c;为建筑赋予了蓬勃的生机与活力&#xff0c;从根本上改变了传统建筑的运行模式&#xff0c;使其朝着高效、智能、舒适的方向大步迈进。那么&#xff0c;楼宇自控究竟在哪些方面为建筑带来了如此显著的变化…...

asp.net Kestrel 和iis区别

Kestrel 和 IIS 都是用于托管 Web 应用程序的服务器&#xff0c;不过它们在多个方面存在显著差异&#xff0c;下面为你详细分析&#xff1a; 1. 所属平台与跨平台能力 Kestrel&#xff1a;是.NET Core 及后续版本的一部分&#xff0c;具备跨平台特性&#xff0c;可在 Windows…...

[原创](Modern C++)现代C++的关键性概念: 优雅地使用现代for循环语句

[作者] 常用网名: 猪头三 出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站 编程生涯: 2001年~至今[共24年] 职业生涯: 22年 开发语言: C/C、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、 开发工具: Visual Studio、Delphi、XCode、C …...

【第42节】windows双机调试环境搭建和SEH原理剖析

目录 一、windows双机调试环境 1.1 双机调试是什么 1.2 准备工作 1.3 配置步骤 1.3.1 安装 VirtualKD 1.3.2 将target文件夹拷贝到虚拟机 1.3.3 在主机上使用vmmon64.exe监控虚拟机 二、SEH 原理剖析 2.1 TEB 与 FS 概述 2.2 手工注册 SEH 一、windows双机调试环境 …...