力扣第235题 二又搜索树的最近公共祖先 c++
题目
235. 二叉搜索树的最近公共祖先
中等 (简单)
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。
思路和解题方法
使用迭代的方式进行查找。首先将
ancestor初始化为根节点root。然后,在一个无限循环中进行以下判断:
- 如果
p->val和q->val都小于ancestor->val,说明p和q都在ancestor的左子树中,因此将ancestor更新为ancestor->left。- 如果
p->val和q->val都大于ancestor->val,说明p和q都在ancestor的右子树中,因此将ancestor更新为ancestor->right。- 如果以上两个条件都不满足,说明
p和q分别位于ancestor的左右子树中,或者其中一个节点就是ancestor。此时,找到了最近公共祖先,退出循环。 最后,返回ancestor即为最近公共祖先的节点。由于输入的二叉搜索树符合规范,且假设
p和q一定存在于树中,因此该算法可以正确找到最近公共祖先。
复杂度
时间复杂度:
O(n)
时间复杂度:O(n),其中 nnn 是给定的二叉搜索树中的节点个数。分析思路与方法一相同。
空间复杂度
O(1)
- 空间复杂度:O(1)。
c++ 代码
class Solution {
public:// 返回二叉搜索树中p和q节点的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* ancestor = root; // 初始化最近公共祖先为根节点rootwhile (true) {if (p->val < ancestor->val && q->val < ancestor->val) { // 如果p、q都小于ancestor,说明p、q在ancestor的左子树中ancestor = ancestor->left; // 将ancestor更新为其左子树的节点}else if (p->val > ancestor->val && q->val > ancestor->val) { // 如果p、q都大于ancestor,说明p、q在ancestor的右子树中ancestor = ancestor->right; // 将ancestor更新为其右子树的节点}else { // 如果p、q分别位于ancestor的左右子树中,或者其中一个节点就是ancestor,则找到了最近公共祖先,退出循环break;}}return ancestor; // 返回最近公共祖先}
};
附递归版本(迭代版本容易懂)
class Solution {
public:// 返回二叉搜索树中p和q节点的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root->val > p->val && root->val > q->val) { // 如果root的值大于p和q的值,则说明p和q都在root的左子树中,继续往root的左子树中搜索return lowestCommonAncestor(root->left, p, q);} else if (root->val < p->val && root->val < q->val) { // 如果root的值小于p和q的值,则说明p和q都在root的右子树中,继续往root的右子树中搜索return lowestCommonAncestor(root->right, p, q);} else {return root; // 否则,root为最近公共祖先,直接返回root}}
};
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
相关文章:
力扣第235题 二又搜索树的最近公共祖先 c++
题目 235. 二叉搜索树的最近公共祖先 中等 (简单) 相关标签 树 深度优先搜索 二叉搜索树 二叉树 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q&…...
时代风口中的Web3.0基建平台,重新定义Web3.0!
近年来,Web3.0概念的广泛兴起,给加密行业带来了崭新的叙事方式,同时也为加密行业提供了更加具有想象力的应用场景与商业空间,并让越来越多的行业从业者们意识到只有更大众化的市场共性需求才能推动加密市场的持续繁荣。当前围绕这…...
React学习笔记 001
什么是React 1.发送请求获取数据 处理数据(过滤、整理格式等) 3.操作DOM呈现页面 react 主要是负责第三部 操作dom 处理页面 数据渲染为HTML视图的开源js库。 好处 避免dom繁琐 组件化 提升复用率 特点 声明式编程: 简单 组件化编程…...
2023 | github无法访问或速度慢的问题解决方案
github无法访问或速度慢的问题解决方案 前言: 最近经常遇到github无法访问, 或者访问特别慢的问题, 在搜索了一圈解决方案后, 有些不再有效了, 但是其中有几个还特别好用, 总结一下. 首选方案 直接在github.com的域名上加一个fast > githubfast.com, 访问的是与github完全相…...
unity各种插件集合(自用)
2D Animation——2D序列帧/骨骼动画相关 2D PSD Importer——psb骨骼动画(unity官方建议使用psb而非psd) (Advanced —show preview package 勾选)出现 2D IK——反向动力学IK Universal RP——升级项目到Urp(通用渲…...
内网收集哈希传递
1.内网收集的前提 获得一个主机权限 补丁提权 可以使用 systeminfo 然后使用python脚本找到缺少的补丁 下载下来 让后使用exp提权 收集信息 路由信息 补丁接口 dns域看一看是不是域控 扫描别的端口 看看有没有内在的web网站 哈希传递 哈希是啥 哈希…...
前端目录笔记
HTML HTML 笔记:初识 HTML(HTML文本标签、文本列表、嵌入图片、背景色、网页链接)-CSDN博客html 笔记:CSS_UQI-LIUWJ的博客-CSDN博客HTML 笔记 表格_UQI-LIUWJ的博客-CSDN博客 javascript JavaScript 笔记 初识JavaScript&…...
Sui主网升级至V1.11.2版本
Sui主网现已升级至V1.11.2版本,同时Sui协议升级至27版本。其他升级要点如下: 对于一些更高级别的交易,更改了一些gas费设置,使其gas费消耗的更快。这些更改不影响以前在网络上运行的任何交易,只是为了确保在开始大量使…...
Mysql-数据库和数据表的基本操作
Mysql数据库和数据表的基本操作 一.数据库 1.创建数据库 创建数据库就是在数据库系统中划分一块空间存储数据 (1)语法 create database 数据库名称;(2)查看数据库 show create database 数据库名;(3)…...
拓扑排序求最长路
P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目要求我们求出第1号到第n号节点之间最长的距离。 我们想到使用拓扑排序来求最长路。 正常来讲,我们应该把1号节点入队列,再出队列,把一号节点能到达的所有的点的入度减一&a…...
sqli-lab靶场通关
文章目录 less-1less-2less-3less-4less-5less-6less-7less-8less-9less-10 less-1 1、提示输入参数id,且值为数字; 2、判断是否存在注入点 id1报错,说明存在 SQL注入漏洞。 3、判断字符型还是数字型 id1 and 11 --id1 and 12 --id1&quo…...
使用 Apache Camel 和 Quarkus 的微服务(五)
【squids.cn】 全网zui低价RDS,免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 在本系列的第三部分中,我们了解了如何在 Minikube 中部署基于 Quarkus/Camel 的微服务,这是最常用的 Kubernetes 本地实现之一。虽然这样的本地…...
Ubuntu磁盘满了,导致黑屏
前言 (1)最近要玩Milk-V Duo,配置环境过程中,发现磁盘小了。于是退出虚拟机,扩大Ubuntu大小,重新开机,发现无法进入Ubuntu界面。 (2)查了很久,后面发现是磁盘…...
安装sklearn包错误解决以及 scikit-learn简介
安装sklearn包错误解决以及 scikit-learn简介 利用 pip install sklearn时出现错误 pip install sklearn Looking in indexes: https://mirrors.aliyun.com/pypi/simple/ Collecting sklearnUsing cached https://mirrors.aliyun.com/pypi/packages/b9/0e/b2a4cfaa9e12b9ca4…...
CSS点击切换或隐藏盒子的卷起、展开效果
<template><div class"main"><el-button click"onCllick">切换</el-button><transition name"slideDown"><div class"info" v-if"isShow">1111</div></transition></di…...
关于信息安全软考的一些记录1
1、网络信息安全的基本属性 机密性:网络信息不泄露给非授权的用户完整性:未经授权必能改的特性可用性:可以及时获取网络信息和服务的特性可控性:责任主体对网络信息系统具有管理、支配的能力【可管理、可支配】扛抵赖性ÿ…...
如何选择UMLChina服务
服务口号:聚焦最后一公里 斐力庇第斯从马拉松跑回雅典报信,虽然已是满身血迹、精疲力尽,但他知道:没有出现在雅典人民面前,前面的路程都是白费。 学到的知识如果不能最终【用】于您自己的项目之中,也同样是…...
关于信息安全软考的记录3
1、网络安全体系的特征 网络安全体系:网络安全保障系统的最高层概念抽象 特征内容整体性网络安全单元按照一定的规则,相互依赖、相互作用而形成人机物一体化的网络安全保护方式协同性通过各种安全机制的相互协作,构建系统性的网络安全保护方…...
API攻防-接口安全SOAPOpenAPIRESTful分类特征导入项目联动检测
文章目录 概述什么是接口? 1、API分类特征SOAP - WSDLWeb services 三种基本元素: OpenApi - Swagger UISpringboot Actuator 2、API检测流程Method:请求方法URL:唯一资源定位符Params:请求参数Authorizationÿ…...
【Docker 内核详解】namespace 资源隔离(二):UTS namespace IPC namespace
namespace 资源隔离(二):UTS namespace & IPC namespace 1.UTS namespace UTS(UNIX Time-sharing System),UTS namespace 提供了 主机名 和 域名 的隔离,这样每个 Docker 容器就可以拥有独…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
