LeetCode 0235.二叉搜索树的最近公共祖先:用搜索树性质(不遍历全部节点)
【LetMeFly】235.二叉搜索树的最近公共祖先:用搜索树性质(不遍历全部节点)
力扣题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
方法一:用搜索树性质(不遍历全部节点)
需要注意的是,这道题给定的二叉树是二叉搜索树。因此对于某个节点root:
- 如果
root.val > p.val并且root.val > q.val,就说明p和q都在root的左子树上。令root = root.left。 - 否则如果
root.val < p.val并且root.val < q.val,就说明p和q都在root的右子树上。令root = root.right。 - 否则,说明
p和q在root的左右子树上或者就是root,root即为p和q的最近公共祖先。
以上。
- 时间复杂度 O ( N ) O(N) O(N),其中 N N N是二叉树节点个数
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution { // AC,83.74%,90.18%
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while (true) {if (root->val < p->val && root->val < q->val) {root = root->right;}else if (root->val > p->val && root->val > q->val) {root = root->left;}else {return root;}}}
};
Python
# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':while True:if root.val < p.val and root.val < q.val:root = root.rightelif root.val > p.val and root.val > q.val:root = root.leftelse:return root
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136279915
相关文章:
LeetCode 0235.二叉搜索树的最近公共祖先:用搜索树性质(不遍历全部节点)
【LetMeFly】235.二叉搜索树的最近公共祖先:用搜索树性质(不遍历全部节点) 力扣题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公…...
【Prometheus】概念和工作原理介绍
目录 一、概述 1.1 prometheus简介 1.2 prometheus特点 1.3 prometheus架构图 1.4 prometheus组件介绍 1、Prometheus Server 2、Client Library 3、pushgateway 4、Exporters 5、Service Discovery 6、Alertmanager 7、grafana 1.5 Prometheus 数据流向 1.6 Pro…...
四川易点慧电子商务有限公司抖音小店:可靠之选,购物新体验
在当今这个网络购物日益盛行的时代,选择一家可靠的电商平台成为了消费者最为关心的问题之一。四川易点慧电子商务有限公司抖音小店作为新兴的电商力量,凭借其独特的魅力和优势,正逐渐成为众多消费者心中的可靠之选。 易点慧电子商务有限公司在…...
SpringBoot自带的tomcat的最大连接数和最大的并发数
先说结果:springboot自带的tomcat的最大并发数是200, 最大连接数是:max-connectionsaccept-count的值 再说一下和连接数相关的几个配置: 以下都是默认值: server.tomcat.threads.min-spare10 server.tomcat.threa…...
TLS1.2抓包解析
1.TLS1.2记录层消息解析 Transport Layer SecurityTLSv1.2 Record Layer: Handshake Protocol: Client HelloContent Type: Handshake (22)Version: TLS 1.0 (0x0301)Length: 253Content Type:消息类型,1个字节。 i 0Version:协议版本&…...
使用两个队列实现栈
在计算机科学中,栈是一种数据结构,它遵循后进先出(LIFO)的原则。这意味着最后一个被添加到栈的元素将是第一个被移除的元素。然而,Java的标准库并没有提供栈的实现,但我们可以使用两个队列来模拟一个栈的行…...
通过ffmpeg实现视频背景色替换
最近遇到一个需求,希望可以将素材视频的绿幕背景替换为指定的颜色,然后通过裁剪,拼接等处理制作一个新的视频。所以替换背景色成为了重要的一环,看能否通过ffmpeg来实现。通过一番搜索尝试,发现方案可行。下面我整理一…...
后轮位置反馈控制与算法仿真实现
文章目录 1. 后轮反馈控制2. 算法原理3. 算法和仿真实现 1. 后轮反馈控制 后轮反馈控制(Rear wheel feedback)算法是利用后轮中心的跟踪偏差来进行转向控制量计算的方法,属于Frenet坐标系的一个应用。通过选择合适的李雅普诺夫函数设计控制率…...
实战 vue3 使用百度编辑器ueditor
前言 在开发项目由于需求vue自带对编辑器不能满足使用,所以改为百度编辑器,但是在网上搜索发现都讲得非常乱,所以写一篇使用流程的文章 提示:以下是本篇文章正文内容,下面案例可供参考 一、下载ueditor编辑器 一个“…...
N种方法解决1(CTF)
这里遇到的问题:一开始采用的base64解码平台有问题;默认解密出的格式为GBK格式;直接复制粘贴发现无法还原图片;又尝试了其他编码的;发现只有hex格式可以保证图片正常还原; 图片是以二进制存储的࿱…...
Istio实战:Istio Kiali部署与验证
目录 前言一、Istio安装小插曲 注意事项 二、Kiali安装三、Istio测试参考资料 前言 前几天我就开始捣腾Istio。前几天在执行istioctl install --set profiledemo -y 的时候老是在第二步就报错了,开始我用的istio版本是1.6.8。 后面查看k8s与istio的版本对应关系后发…...
ASPxGridView中使用PopupEditForm表单字段联动填充
c#中devexpress的控件ASPxGridView中使用PopupEditForm表单字段联动填充 //选择项目名称,自动填充项目编号 <Columns><dx:GridViewDataTextColumn FieldName"id" ReadOnly"True" VisibleIndex"0" Visible"False"…...
基于Pytorch的猫狗图片分类【深度学习CNN】
猫狗分类来源于Kaggle上的一个入门竞赛——Dogs vs Cats。为了加深对CNN的理解,基于Pytorch复现了LeNet,AlexNet,ResNet等经典CNN模型,源代码放在GitHub上,地址传送点击此处。项目大纲如下: 文章目录 一、问题描述二、数据集处理…...
flutter sliver 多种滚动组合开发指南
flutter sliver 多种滚动组合开发指南 视频 https://youtu.be/4mho1kZ_YQU https://www.bilibili.com/video/BV1WW4y1d7ZC/ 前言 有不少同学工作中遇到需要把几个不同滚动行为组件(顶部 appBar、内容固定块、tabBar 切换、tabBarView视图、自适应高度、横向滚动&a…...
kafka生产者2
1.数据可靠 • 0:生产者发送过来的数据,不需要等数据落盘应答。 风险:leader挂了之后,follower还没有收到消息。。。。 • 1:生产者发送过来的数据,Leader收到数据后应答。 风险:leader应答…...
【LNMP】云导航项目部署及环境搭建(复杂)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、项目介绍1.1项目环境架构LNMP1.2项目代码说明 二、项目环境搭建2.1 Nginx安装2.2 php安装2.3 nginx配置和php配置2.3.1 修改nginx文件2.3.2 修改vim /etc/p…...
nginx之状态页 日志分割 自定义图表 证书
5.1 网页的状态页 基于nginx 模块 ngx_http_stub_status_module 实现,在编译安装nginx的时候需要添加编译参数 --with-http_stub_status_module,否则配置完成之后监测会是提示语法错误注意: 状态页显示的是整个服务器的状态,而非虚拟主机的状态 server{…...
数字人的未来:数字人对话系统 Linly-Talker + 克隆语音 GPT-SoVITS
🚀数字人的未来:数字人对话系统 Linly-Talker 克隆语音 GPT-SoVITS https://github.com/Kedreamix/Linly-Talker 2023.12 更新 📆 用户可以上传任意图片进行对话 2024.01 更新 📆 令人兴奋的消息!我现在已经将强…...
SpringMVC 学习(五)之域对象
目录 1 域对象介绍 2 向 request 域对象共享数据 2.1 通过 ServletAPI (HttpServletRequest) 向 request 域对象共享数据 2.2 通过 ModelAndView 向 request 域对象共享数据 2.3 通过 Model 向 request 域对象共享数据 2.4 通过 map 向 request 域对象共享数据 2.5 通过…...
✅技术社区项目—JWT身份验证
通用的JWT鉴权方案 JWT鉴权流程 基本流程分三步: ● 用户登录成功之后,后端将生成的jwt返回给前端,然后前端将其保存在本地缓存; ● 之后前端与后端的交互时,都将iwt放在请求头中,比如可以将其放在Http的身份认证的请求头 Author…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
