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…...
帆软报表FineReport连接Elasticsearch避坑指南:从插件安装到SQL编写的完整流程
帆软报表FineReport连接Elasticsearch全流程实战指南 在企业级数据分析领域,帆软报表FineReport与Elasticsearch的集成能够显著提升海量数据的可视化分析能力。本文将基于实际项目经验,系统梳理从环境准备到生产部署的完整链路,特别针对配置过…...
深入PEX8796:从Serdes到Virtual Switch,图解PCIe交换芯片的三种工作模式
深入解析PEX8796:PCIe交换芯片的架构设计与模式创新 在高速数据传输领域,PCIe交换芯片如同交通枢纽般连接着计算系统的各个组件。作为PLX公司(现已被博通收购)的经典之作,PEX8796凭借其灵活的架构设计和多样化的操作模…...
C++内存可视化利器:silicondawn/memory-viewer库实战指南
1. 项目概述与核心价值最近在调试一个涉及复杂内存操作的C项目时,我又一次陷入了“内存黑盒”的困境。指针指向的数据结构到底对不对?序列化后的字节流里某个字段的值是不是我预期的?手动printf或者断点查看十六进制,效率低不说&a…...
Go语言WebSocket服务器tocket:轻量级高性能实时通信方案
1. 项目概述:一个轻量级、高性能的WebSocket服务器 最近在折腾一个需要实时双向通信的物联网项目,传统的HTTP轮询方案在延迟和服务器开销上都不太理想,WebSocket自然就成了首选。在技术选型时,我习惯性地会去GitHub上搜罗一番&…...
Arm Neoverse CMN-650架构与编程实践详解
1. CMN-650架构概述Arm Neoverse CMN-650是一种基于Mesh拓扑的一致性互连网络,专为多核处理器和加速器系统设计。作为SoC内部的数据高速公路,它通过优化的路由算法和一致性协议,实现了高带宽、低延迟的核间通信。1.1 核心组件解析CMN-650由多…...
基于SpringBoot的门禁与访客管理系统毕业设计
博主介绍:✌ 专注于Java,python,✌关注✌私信我✌具体的问题,我会尽力帮助你。一、研究目的本研究旨在构建一个基于Spring Boot框架的门禁与访客管理系统以解决传统门禁系统在智能化管理方面存在的局限性。当前多数门禁系统仍采用封闭式架构设计导致数据…...
NotebookLM畜牧业研究辅助落地手册(2024畜牧AI工具箱首发版)
更多请点击: https://intelliparadigm.com 第一章:NotebookLM畜牧业研究辅助落地手册(2024畜牧AI工具箱首发版)概述 NotebookLM 是 Google 推出的基于用户上传文档构建可信问答与推理能力的 AI 助手,其“引用溯源”与…...
15分钟掌握ColorUI:打造高颜值小程序的终极色彩解决方案
15分钟掌握ColorUI:打造高颜值小程序的终极色彩解决方案 【免费下载链接】coloruicss 鲜亮的高饱和色彩,专注视觉的小程序组件库 项目地址: https://gitcode.com/gh_mirrors/co/coloruicss 还在为小程序界面设计而烦恼吗?ColorUI色彩系…...
NotebookLM辅助CRISPR靶点筛选实操:从NCBI SRA原始数据到脱靶风险摘要,限时开放实验日志包
更多请点击: https://intelliparadigm.com 第一章:NotebookLM生物学研究辅助 NotebookLM 是 Google 推出的基于 LLM 的研究型笔记工具,专为科研人员设计,其核心能力在于对私有文档(如 PDF、TXT)进行深度语…...
STM32CubeMX实战:FSMC高效驱动ILI9488 LCD屏(基于STM32F407)
1. 环境准备与硬件连接 在开始配置FSMC驱动ILI9488 LCD屏之前,我们需要准备好开发环境和硬件设备。我使用的是STM32F407VET6核心板搭配3.5寸320x480分辨率的ILI9488控制器TFT LCD屏幕。这种组合在工业控制和消费电子领域非常常见,性价比高且性能稳定。 硬…...
