二叉树的最近公共祖先LCA
系列题目
236. 二叉树的最近公共祖先
1676. 二叉树的最近公共祖先IV
1644. 二叉树的最近公共祖先 II
235. 二叉搜索树的最近公共祖先
1650. 二叉树的最近公共祖先 III
class LowestCommonAncestor:"""236. 二叉树的最近公共祖先题目强调p和q一定存在于二叉树中,区别于1644题https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/"""def solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def find(root, val1, val2):if not root:return None# 这里对应情况二if root.val == val1 or root.val == val2:return rootleft = find(root.left, val1, val2)right = find(root.right, val1, val2)# 这里对应情况一, 【后序位置,已经知道左右子树是否存在目标值】if left and right:# 当前节点是 LCA 节点return rootreturn left if left else rightreturn find(root, p.val, q.val)
class LowestCommonAncestor2:"""1676. 二叉树的最近公共祖先IV这道题把p和q换成了包含若干个节点的列表,同样这些列表里的所有节点一定存在于二叉树中,区别于1644题https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iv/"""def solution(self, root: 'TreeNode', nodes: List[TreeNode]) -> 'TreeNode':# 将列表转化成哈希集合,便于判断元素是否存在values = set()for node in nodes:values.add(node.value)self.find(root, values)def find(self, root: 'TreeNode', values):if not root:return None# 前序位置if root.value in values:return rootleft = self.find(root.left, values)right = self.find(root.right, values)# 后序位置,已经知道左右子树是否存在目标值if left and right:return rootreturn left if left else right
class LowestCommonAncestor3:"""1644. 二叉树的最近公共祖先 II输入一棵不含重复值的二叉树的,以及两个节点 p 和 q,这道题区别于236题,给定的两个节点p和q不一定存在于树中,不存在返回空指针,存在则返回最近公共祖先节点https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii/"""def __init__(self):# 用于记录p和q是否存在于二叉树中self.foundP = Falseself.foundQ = Falsedef solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':res = self.find(root, p.val, q.val)if not self.foundP or not self.foundQ:return Nonereturn resdef find(self, root, val1, val2):"""在二叉树中寻找 val1 和 val2 的最近公共祖先节点:param root::param val1::param val2::return:"""if not root:return Noneleft = self.find(root.left, val1, val2)right = self.find(root.right, val1, val2)# 后续位置,判断当前节点是不是LCAif left and right:# 当前节点是 LCA 节点return root# 后续位置,判断当前节点是不是目标值if root.value == val1 or root.value == val2:if root.value == val1:self.foundP = Trueif root.value == val2:self.foundQ = Truereturn rootreturn left if left else right
class LowestCommonAncestor4:"""235. 二叉搜索树的最近公共祖先这是一颗BST树,要充分利用 左子节点 < 父节点 < 右子节点 的大小关系寻找LCAhttps://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/"""def solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':val1 = min(p.val, q.val)val2 = max(p.val, q.val)return self.find(root, val1, val2)# 在 BST 中寻找 val1 和 val2 的最近公共祖先节点def find(self, root, val1, val2):if not root:return Noneif root.val > val2:return self.find(root.left, val1, val2)elif root.val < val1:return self.find(root.right, val1, val2)else: # val1 <= root.val <= val2return root
class LowestCommonAncestor5:"""1650. 二叉树的最近公共祖先 III这道题,给出的二叉树节点比较特殊,包括指向父节点的指针,和寻找两个单链表的相交的起始点做法一样【160. 相交链表】二叉树的最近公共祖先 IIIhttps://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iii/"""class Node:def __init__(self):self.val = Noneself.left = Noneself.right = Noneself.parent = Nonedef solution(self, p: 'Node', q: 'Node') -> 'Node':# 链表双指针技巧a, b = p, qwhile a != b:# a 走一步,如果走到根节点,转到 q 节点if not a:a = qelse:a = a.parent# b 走一步,如果走到根节点,转到 p 节点if not b:b = pelse:b = b.parentreturn a
相关文章:

二叉树的最近公共祖先LCA
系列题目 236. 二叉树的最近公共祖先 1676. 二叉树的最近公共祖先IV 1644. 二叉树的最近公共祖先 II 235. 二叉搜索树的最近公共祖先 1650. 二叉树的最近公共祖先 III class LowestCommonAncestor:"""236. 二叉树的最近公共祖先题目强调p和q一定存在于二叉树中&…...

AWS SAA知识点整理(作成中)
共通 一些信息已经更新了,但参考题的答案还是旧的。 比如: S3的最大读写性能已经提高到 3,500 PUT/COPY/POST/DELETE or 5,500 GET/HEAD requests per second 并且不再要求使用random prefix 题目中有时候会让选择Not violation 不合适的一项ÿ…...
C++模板大全(持续更新,依不同网站整理而成)
C模板大全 基本模板快读快写快读快写火车头缺省源 基本算法暴力枚举模拟贪心二分三分尺取法分治前缀和差分递推递归倍增排序sort冒泡排序桶排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序基数排序 基础数据结构栈队列哈希链表单向链表双向链表 单调栈单调队列 高…...

《CTFshow-Web入门》10. Web 91~110
Web 入门 索引web91题解总结 web92题解总结 web93题解 web94题解 web95题解 web96题解 web97题解 web98题解 web99题解总结 web100题解 web101题解 web102题解 web103题解 web104题解 web105题解总结 web106题解 web107题解 web108题解 web109题解 web110题解 ctf - web入门 索…...

计组--总线
一、概念 总线是一组能为多个部件分时共享的公共信息传送线路。 共享是指总线上可以挂接多个部件,各个部件之间互相交换的信息都可以通过这组线路分时共享。 分时是指同一时刻只允许有一个部件向总线发送信息,如果系统中有多个部件,则它们…...
Git中的HEAD
Git中的HEAD HEAD^数字:表示当前提交的父提交,具体是第几个父提交通过数字指定,HEAD^1第一个父提交,该语法只 能用于合并(merge)的提交记录,因为一个通过合并产生的commit对象才有多个父提交。 HEAD~数字࿱…...

软件设计师_数据库系统_学习笔记
文章目录 3.1 数据库模式3.1.1 三级模式 两级映射3.1.2 数据库设计过程 3.2 ER模型3.3 关系代数与元组演算3.4 规范化理论3.5 并发控制3.6 数据库完整性约束3.7 分布式数据库3.8 数据仓库与数据挖掘 3.1 数据库模式 3.1.1 三级模式 两级映射 内模式直接与物理数据库相关联的 定…...

毛玻璃态计算器
效果展示 页面结构组成 从上述的效果可以看出,计算机的页面比较规整,适合grid布局。 CSS3 知识点 grid 布局 实现计算机布局 <div class"container"><form class"calculator" name"calc"><input type…...

常说的I2C协议是干啥的(电子硬件)
I2C(Inter-Integrated circuit)协议是电子传输信号中常用的一种协议。 它是一种两线式串行双向总线,用于连接微控制器和外部设备,也因为它所需的引脚数只需要两条(CLK和DATA),硬件实现简单&…...

C/C++进程超详细详解【中部分】(系统性学习day07)
目录 前言 一、守护进程 1.概念 2.守护进程创建的原理(如图清晰可见) 3.守护进程的实现(代码块) 二、dup和dup2 1,复制文件描述符 2.文件描述符重定向 三、系统日志 1,打开日志 2,向日…...
S型速度曲线轨迹规划(约束条件为速度和位移)
S型速度曲线规划的基础知识可以查看下面这篇博客: 带平滑功能的斜坡函数(多段曲线控温纯S型曲线SCL源代码+完整算法分析)_RXXW_Dor的博客-CSDN博客PLC运动控制基础系列之梯形速度曲线,可以参看下面这篇博客:PLC运动控制基础系列之梯形速度曲线_RXXW_Dor的博客-CSDN博客运…...

从零手搓一个【消息队列】实现数据的硬盘管理和内存管理(线程安全)
文章目录 一、硬盘管理1, 创建 DiskDataCenter 类2, init() 初始化3, 封装交换机4, 封装队列5, 关于绑定6, 关于消息 二、内存管理1, 数据结构的设计2, 创建 MemoryDataCenter 类3, 关于交换机4, 关于队列5, 关于绑定6, 关于消息7, 恢复数据 三、小结 创建 Spring Boot 项目, S…...

自动驾驶中的感知模型:实现安全与智能驾驶的关键
自动驾驶中的感知模型:实现安全与智能驾驶的关键 文章目录 引言感知模型的作用感知模型的技术安全与挑战结论 2023星火培训【专项营】Apollo开发者社区布道师倾力打造,包含PnC、新感知等的全新专项课程上线了。理论与实践相结合,全新的PnC培训…...

【CVPR 2023】DSVT: Dynamic Sparse Voxel Transformer with Rotated Sets
文章目录 开场白效果意图 重点VoxelNet: End-to-End Learning for Point Cloud Based 3D Object DetectionX-Axis DSVT LayerY-Axis DSVT Layer Dynamic Sparse Window AttentionDynamic set partitionRotated set attention for intra-window feature propagation.Hybrid wind…...

MySQL超入门(1)__迅速上手掌握MySQL
# 1.选择语句 # 注意事项:MySQL不区分大小写,SELECT * 代表选择全部 // 测试一 USE sql_store; -- 使用 sql_store库 SELECT * FROM customers -- 查询customers表 WHERE customer_id 1 OR customer_id 4 -- 条件判断为customer_id 1或customer_id …...

四、浏览器渲染过程,DOM,CSSDOM,渲染,布局,绘制详细介绍
知识点: 1、为什么不能先执行 js文件?? 我们不能先执行JS文件,必须等到CSSOM构建完成了才能执行JS文件,因为前面已经说过渲染树是需要DOM和CSSOM构建完成了以后才能构建,而且JS是可以操控CSS样式的&#…...

2021-06-10 51单片机设计一个蜂鸣器报警电路每秒
缘由求助一下谢谢啦51单片机_嵌入式-CSDN问答设计一个蜂鸣器报警电路,按下K1,蜂鸣器响一声,按下K2,蜂鸣器响三声,按下K3,蜂鸣器长鸣。要求响声和间隔的时间均为1秒,长鸣不限时,但是此时应设置一…...
D‘Agostino-Pearson正态检验|偏度skewness和峰度kurtosis
DAgostino-Pearson检验(也称为DAgostino和Pearson正态性检验)是一种用于检验数据是否符合正态分布的统计检验方法。它基于数据的样本统计量,主要包括偏度(skewness)和峰度(kurtosis),…...

基于树莓派CM4制作img系统镜像批量制作TF卡
文章目录 前言1. 环境与工具2. 制作镜像3. 烧录镜像4. 总结 前言 树莓派烧录完系统做定制化配置比较费时间。在面对大批量的树莓派要配置,那时间成本是非常巨大的。第一次配置完可以说是摸着石头过河,但是会弄了以后再配置,都是一些重复性操…...

【中秋国庆不断更】OpenHarmony组件内状态变量使用:@State装饰器
State装饰的变量,或称为状态变量,一旦变量拥有了状态属性,就和自定义组件的渲染绑定起来。当状态改变时,UI会发生对应的渲染改变。 在状态变量相关装饰器中,State是最基础的,使变量拥有状态属性的装饰器&am…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...

自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...

Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...