力扣第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 容器就可以拥有独…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
