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

二叉树的最近公共祖先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知识点整理(作成中)

共通 一些信息已经更新了&#xff0c;但参考题的答案还是旧的。 比如&#xff1a; S3的最大读写性能已经提高到 3,500 PUT/COPY/POST/DELETE or 5,500 GET/HEAD requests per second 并且不再要求使用random prefix 题目中有时候会让选择Not violation 不合适的一项&#xff…...

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入门 索…...

计组--总线

一、概念 总线是一组能为多个部件分时共享的公共信息传送线路。 共享是指总线上可以挂接多个部件&#xff0c;各个部件之间互相交换的信息都可以通过这组线路分时共享。 分时是指同一时刻只允许有一个部件向总线发送信息&#xff0c;如果系统中有多个部件&#xff0c;则它们…...

Git中的HEAD

Git中的HEAD HEAD^数字&#xff1a;表示当前提交的父提交&#xff0c;具体是第几个父提交通过数字指定&#xff0c;HEAD^1第一个父提交&#xff0c;该语法只 能用于合并(merge)的提交记录&#xff0c;因为一个通过合并产生的commit对象才有多个父提交。 HEAD~数字&#xff1…...

软件设计师_数据库系统_学习笔记

文章目录 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 三级模式 两级映射 内模式直接与物理数据库相关联的 定…...

毛玻璃态计算器

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

常说的I2C协议是干啥的(电子硬件)

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

C/C++进程超详细详解【中部分】(系统性学习day07)

目录 前言 一、守护进程 1.概念 2.守护进程创建的原理&#xff08;如图清晰可见&#xff09; 3.守护进程的实现&#xff08;代码块&#xff09; 二、dup和dup2 1&#xff0c;复制文件描述符 2.文件描述符重定向 三、系统日志 1&#xff0c;打开日志 2&#xff0c;向日…...

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…...

自动驾驶中的感知模型:实现安全与智能驾驶的关键

自动驾驶中的感知模型&#xff1a;实现安全与智能驾驶的关键 文章目录 引言感知模型的作用感知模型的技术安全与挑战结论 2023星火培训【专项营】Apollo开发者社区布道师倾力打造&#xff0c;包含PnC、新感知等的全新专项课程上线了。理论与实践相结合&#xff0c;全新的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.选择语句 # 注意事项&#xff1a;MySQL不区分大小写&#xff0c;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,渲染,布局,绘制详细介绍

知识点&#xff1a; 1、为什么不能先执行 js文件&#xff1f;&#xff1f; 我们不能先执行JS文件&#xff0c;必须等到CSSOM构建完成了才能执行JS文件&#xff0c;因为前面已经说过渲染树是需要DOM和CSSOM构建完成了以后才能构建&#xff0c;而且JS是可以操控CSS样式的&#…...

2021-06-10 51单片机设计一个蜂鸣器报警电路每秒

缘由求助一下谢谢啦51单片机_嵌入式-CSDN问答设计一个蜂鸣器报警电路&#xff0c;按下K1&#xff0c;蜂鸣器响一声&#xff0c;按下K2&#xff0c;蜂鸣器响三声&#xff0c;按下K3,蜂鸣器长鸣。要求响声和间隔的时间均为1秒&#xff0c;长鸣不限时&#xff0c;但是此时应设置一…...

D‘Agostino-Pearson正态检验|偏度skewness和峰度kurtosis

DAgostino-Pearson检验&#xff08;也称为DAgostino和Pearson正态性检验&#xff09;是一种用于检验数据是否符合正态分布的统计检验方法。它基于数据的样本统计量&#xff0c;主要包括偏度&#xff08;skewness&#xff09;和峰度&#xff08;kurtosis&#xff09;&#xff0c…...

基于树莓派CM4制作img系统镜像批量制作TF卡

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

【中秋国庆不断更】OpenHarmony组件内状态变量使用:@State装饰器

State装饰的变量&#xff0c;或称为状态变量&#xff0c;一旦变量拥有了状态属性&#xff0c;就和自定义组件的渲染绑定起来。当状态改变时&#xff0c;UI会发生对应的渲染改变。 在状态变量相关装饰器中&#xff0c;State是最基础的&#xff0c;使变量拥有状态属性的装饰器&am…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...