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

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,就说明pq都在root的左子树上。令root = root.left
  • 否则如果root.val < p.val并且root.val < q.val,就说明pq都在root的右子树上。令root = root.right
  • 否则,说明pqroot的左右子树上或者就是rootroot即为pq的最近公共祖先。

以上。

  • 时间复杂度 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.二叉搜索树的最近公共祖先&#xff1a;用搜索树性质&#xff08;不遍历全部节点&#xff09; 力扣题目链接&#xff1a;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…...

四川易点慧电子商务有限公司抖音小店:可靠之选,购物新体验

在当今这个网络购物日益盛行的时代&#xff0c;选择一家可靠的电商平台成为了消费者最为关心的问题之一。四川易点慧电子商务有限公司抖音小店作为新兴的电商力量&#xff0c;凭借其独特的魅力和优势&#xff0c;正逐渐成为众多消费者心中的可靠之选。 易点慧电子商务有限公司在…...

SpringBoot自带的tomcat的最大连接数和最大的并发数

先说结果&#xff1a;springboot自带的tomcat的最大并发数是200&#xff0c; 最大连接数是&#xff1a;max-connectionsaccept-count的值 再说一下和连接数相关的几个配置&#xff1a; 以下都是默认值&#xff1a; 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&#xff1a;消息类型&#xff0c;1个字节。 i 0Version&#xff1a;协议版本&…...

使用两个队列实现栈

在计算机科学中&#xff0c;栈是一种数据结构&#xff0c;它遵循后进先出&#xff08;LIFO&#xff09;的原则。这意味着最后一个被添加到栈的元素将是第一个被移除的元素。然而&#xff0c;Java的标准库并没有提供栈的实现&#xff0c;但我们可以使用两个队列来模拟一个栈的行…...

通过ffmpeg实现视频背景色替换

最近遇到一个需求&#xff0c;希望可以将素材视频的绿幕背景替换为指定的颜色&#xff0c;然后通过裁剪&#xff0c;拼接等处理制作一个新的视频。所以替换背景色成为了重要的一环&#xff0c;看能否通过ffmpeg来实现。通过一番搜索尝试&#xff0c;发现方案可行。下面我整理一…...

后轮位置反馈控制与算法仿真实现

文章目录 1. 后轮反馈控制2. 算法原理3. 算法和仿真实现 1. 后轮反馈控制 后轮反馈控制&#xff08;Rear wheel feedback&#xff09;算法是利用后轮中心的跟踪偏差来进行转向控制量计算的方法&#xff0c;属于Frenet坐标系的一个应用。通过选择合适的李雅普诺夫函数设计控制率…...

实战 vue3 使用百度编辑器ueditor

前言 在开发项目由于需求vue自带对编辑器不能满足使用&#xff0c;所以改为百度编辑器&#xff0c;但是在网上搜索发现都讲得非常乱&#xff0c;所以写一篇使用流程的文章 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、下载ueditor编辑器 一个“…...

N种方法解决1(CTF)

这里遇到的问题&#xff1a;一开始采用的base64解码平台有问题&#xff1b;默认解密出的格式为GBK格式&#xff1b;直接复制粘贴发现无法还原图片&#xff1b;又尝试了其他编码的&#xff1b;发现只有hex格式可以保证图片正常还原&#xff1b; 图片是以二进制存储的&#xff1…...

Istio实战:Istio Kiali部署与验证

目录 前言一、Istio安装小插曲 注意事项 二、Kiali安装三、Istio测试参考资料 前言 前几天我就开始捣腾Istio。前几天在执行istioctl install --set profiledemo -y 的时候老是在第二步就报错了&#xff0c;开始我用的istio版本是1.6.8。 后面查看k8s与istio的版本对应关系后发…...

ASPxGridView中使用PopupEditForm表单字段联动填充

c#中devexpress的控件ASPxGridView中使用PopupEditForm表单字段联动填充 //选择项目名称&#xff0c;自动填充项目编号 <Columns><dx:GridViewDataTextColumn FieldName"id" ReadOnly"True" VisibleIndex"0" Visible"False"…...

基于Pytorch的猫狗图片分类【深度学习CNN】

猫狗分类来源于Kaggle上的一个入门竞赛——Dogs vs Cats。为了加深对CNN的理解&#xff0c;基于Pytorch复现了LeNet,AlexNet,ResNet等经典CNN模型&#xff0c;源代码放在GitHub上&#xff0c;地址传送点击此处。项目大纲如下&#xff1a; 文章目录 一、问题描述二、数据集处理…...

flutter sliver 多种滚动组合开发指南

flutter sliver 多种滚动组合开发指南 视频 https://youtu.be/4mho1kZ_YQU https://www.bilibili.com/video/BV1WW4y1d7ZC/ 前言 有不少同学工作中遇到需要把几个不同滚动行为组件&#xff08;顶部 appBar、内容固定块、tabBar 切换、tabBarView视图、自适应高度、横向滚动&a…...

kafka生产者2

1.数据可靠 • 0&#xff1a;生产者发送过来的数据&#xff0c;不需要等数据落盘应答。 风险&#xff1a;leader挂了之后&#xff0c;follower还没有收到消息。。。。 • 1&#xff1a;生产者发送过来的数据&#xff0c;Leader收到数据后应答。 风险&#xff1a;leader应答…...

【LNMP】云导航项目部署及环境搭建(复杂)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、项目介绍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 实现&#xff0c;在编译安装nginx的时候需要添加编译参数 --with-http_stub_status_module&#xff0c;否则配置完成之后监测会是提示语法错误注意: 状态页显示的是整个服务器的状态,而非虚拟主机的状态 server{…...

数字人的未来:数字人对话系统 Linly-Talker + 克隆语音 GPT-SoVITS

&#x1f680;数字人的未来&#xff1a;数字人对话系统 Linly-Talker 克隆语音 GPT-SoVITS https://github.com/Kedreamix/Linly-Talker 2023.12 更新 &#x1f4c6; 用户可以上传任意图片进行对话 2024.01 更新 &#x1f4c6; 令人兴奋的消息&#xff01;我现在已经将强…...

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鉴权流程 基本流程分三步: ● 用户登录成功之后&#xff0c;后端将生成的jwt返回给前端&#xff0c;然后前端将其保存在本地缓存; ● 之后前端与后端的交互时&#xff0c;都将iwt放在请求头中&#xff0c;比如可以将其放在Http的身份认证的请求头 Author…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...