185.二叉树:二叉搜索树的最近公共祖先(力扣)

代码解决

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
public:// 函数用于寻找二叉搜索树中节点 p 和 q 的最低公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点为空,返回空if(root == NULL) return NULL;// 如果当前节点的值大于 p 和 q 的值,说明 p 和 q 都在左子树if(root->val > p->val && root->val > q->val){// 递归查找左子树中的 LCATreeNode* left1 = lowestCommonAncestor(root->left, p, q);// 如果在左子树中找到了 LCA,直接返回if(left1 != NULL) return left1;}// 如果当前节点的值小于 p 和 q 的值,说明 p 和 q 都在右子树if(root->val < p->val && root->val < q->val){// 递归查找右子树中的 LCATreeNode* right1 = lowestCommonAncestor(root->right, p, q);return right1; // 返回右子树中的 LCA}// 如果当前节点的值介于 p 和 q 之间,或者等于 p 或 q 的值,当前节点即为 LCAreturn root;}
};

代码使用了递归的方法。主要思路是首先判断当前节点是否为空,如果为空,返回空。然后,根据 p 和 q 的值与当前节点的值的关系,递归地在左子树或右子树中寻找这两个节点。如果当前节点的值大于 p 和 q 的值,则 p 和 q 都在左子树;如果当前节点的值小于 p 和 q 的值,则 p 和 q 都在右子树;如果当前节点的值介于 p 和 q 之间,或者等于 p 或 q 的值,则当前节点即为最低公共祖先。

这里简要解释一下代码的工作流程:

  1. 首先判断当前节点是否为空,如果为空,返回空。
  2. 根据 p 和 q 的值与当前节点的值的关系,决定在左子树或右子树中寻找这两个节点。
  3. 递归地在选定的子树中寻找节点 p 和 q。
  4. 根据递归的结果,判断当前节点是否为最低公共祖先,并返回结果。

这个算法的时间复杂度是 O(h),其中 h 是树的高度。在最坏的情况下,可能需要遍历整个树来找到最低公共祖先。空间复杂度也是 O(h),因为需要存储递归调用的栈。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/348733.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【python】OpenCV GUI——Trackbar(14.2)

学习来自 OpenCV基础&#xff08;12&#xff09;OpenCV GUI中的鼠标和滑动条 文章目录 GUI 滑条介绍cv2.createTrackbar 介绍牛刀小试 GUI 滑条介绍 GUI滑动条是一种直观且快速的调节控件&#xff0c;主要用于改变一个数值或相对值。以下是关于GUI滑动条的详细介绍&#xff1a…

如何利用智能家居打造一个“会呼吸的家”?一体化电动窗帘

如何利用智能家居打造一个“会呼吸的家”&#xff1f;一体化电动窗帘 史新华 隐藏式一体化智能电动窗帘与市面上其他窗帘不同的是&#xff0c;电机内置于轨道之中&#xff0c;一体化&#xff0c;美观、安静、滑动顺畅。 每次都会自动打开和关闭&#xff0c;相当漂亮。 众多家庭…

2002-2023年款别克君威 君威GS维修手册和电路图资料更新

经过整理&#xff0c;2002-2023年款别克君威 君威GS全系列已经更新至汽修帮手资料库内&#xff0c;覆盖市面上99%车型&#xff0c;包括维修手册、电路图、新车特征、车身钣金维修数据、全车拆装、扭力、发动机大修、发动机正时、保养、电路图、针脚定义、模块传感器、保险丝盒图…

双Token方案实现Token自动续期(基于springboot+vue前后端分离项目)

文章目录 前言一、双Token方案介绍1. 令牌类型与功能2.双Token方案的优点3.实现流程 二、具体实现1.后端实现1.1 jwt工具类1.2 响应工具类1.3 实体类1.4 过滤器1.5 controller1.6 启动类 2、前端实现2.1 登录页面2.2 index页面2.3 请求拦截器和响应拦截器 效果展示 前言 更多j…

短剧APP小程序开发之小程序内存管理挑战:短剧缓存与释放策略探讨(第二篇)

在上一篇帖子中&#xff0c;我们探讨了小程序内存管理的限制以及缓存策略的设计。本篇将进一步探讨释放策略的具体实现以及优化方案&#xff0c;以支持大量短剧内容的加载和播放。 释放策略的具体实现 监听内存警告&#xff1a;小程序提供了监听内存警告的API&#xff0c;开发…

【译】SQLAlchemy文档:SQLAlchemy 统一教程

SQLAlchemy Unified Tutorial SQLAlchemy 是 Python SQL工具包和ORM&#xff0c;它为应用程序开发人员提供了 SQL 的全部功能和灵活性。它提供了一整套企业级持久性模式&#xff0c;专为高效和高性能的数据库访问而设计。 SQLAlchemy呈现为两层API&#xff1a;Core和ORM&…

【记录】ChatGLM3-6B大模型部署、微调(一):部署

ChatGLM3介绍 源码连接&#xff1a; ChatGLM3 是智谱AI和清华大学 KEG 实验室联合发布的对话预训练模型。ChatGLM3-6B 是 ChatGLM3 系列中的开源模型&#xff0c;在保留了前两代模型对话流畅、部署门槛低等众多优秀特性的基础上&#xff0c;ChatGLM3-6B 引入了如下特性&#xf…

如何高效管理和监控 Elasticsearch 别名及索引?

0、引言 在 Elasticsearch 项目中&#xff0c;管理和监控索引是开发者的一项重要任务。 尤其是当我们需要在项目的管理部分展示索引和别名的统计信息时&#xff0c;了解如何有效地列出这些别名和索引显得尤为重要。 本篇博客将介绍几种在 Elasticsearch 中列出别名和索引的方法…

7.Nginx动静分离

介绍 把动态和静态请求分开,不能理解成只是单纯的把动态页面和静态页面物理分离。 动静分离从目前实现角度分为两种: 1.纯粹把静态文件独立成单独的域名,放在独立的静态资源服务器上,目前主流推崇的方案。 2.动态和静态文件混合在一起发布,通过nginx来分开。 通过loc…

【微信小程序】事件传参的两种方式

文章目录 1.什么是事件传参2.data-*方式传参3.mark自定义数据 1.什么是事件传参 事件传参:在触发事件时&#xff0c;将一些数据作为参数传递给事件处理函数的过程&#xff0c;就是事件传参 在微信小程序中&#xff0c;我们经常会在组件上添加一些自定义数据&#xff0c;然后在…

毕业年薪20w起!25届最近5南京邮电大学自动化考研院校分析

南京邮电大学 目录 一、学校学院专业简介 二、考试科目指定教材 三、近5年考研分数情况 四、近5年招生录取情况 五、最新一年分数段图表 六、历年真题PDF 七、初试大纲复试大纲 八、学费&奖学金&就业方向 一、学校学院专业简介 二、考试科目指定教材 1、考试…

点云格式转化:将 ros PointCloud2格式数据转为livox CustomMsg格式

前言 览沃科技有限公司&#xff08;Livox&#xff09;成立于2016年。为了革新激光雷达行业&#xff0c;Livox致力于提供高性能、低成本的激光雷达传感器。通过降低使用门槛和生产成本&#xff0c;Livox将激光雷达技术集成到更多产品和应用之中&#xff0c;从而为自动驾驶、智慧…

数据挖掘丨轻松应用RapidMiner机器学习内置数据分析案例模板详解(下篇)

RapidMiner 案例模板 RapidMiner 机器学习平台提供了一个可视化的操作界面&#xff0c;允许用户通过拖放的方式构建数据分析流程。RapidMiner目前内置了 13 种案例模板&#xff0c;这些模板是预定义的数据分析流程&#xff0c;可以帮助用户快速启动和执行常见的数据分析任务。 …

AI “黏土画风”轻松拿捏,手把手带你云端部署 ComfyUI

作者&#xff1a;鸥弋、筱姜 AI 绘画领域&#xff0c;Stable Diffusion WebUI、Midjourney 、DALL-E 都聚拢了一大批的应用开发者和艺术创作者。ComfyUI 出现时间略晚&#xff0c;但是它让创作者通过工作流的方式&#xff0c;实现自动化水平更高的 AI 生图流程&#xff0c;一面…

ISO17025认证是什么?怎么做?

ISO17025认证是一种国际通用的实验室质量管理体系认证&#xff0c;其目标是确保实验室的技术能力、管理水平以及测试结果的可靠性和准确性达到国际认可的标准。该认证由国际标准化组织&#xff08;ISO&#xff09;和国际电工委员会&#xff08;IEC&#xff09;联合发布&#xf…

不停“整活”的零食很忙,怎么就跨入万店时代了?

6月12日&#xff0c;合并后的零食很忙、赵一鸣零食宣布&#xff0c;全国门店总数已突破10000家。同时&#xff0c;集团名称也变更为鸣鸣很忙集团。根据第三方机构弗若斯特沙利文认证&#xff0c;鸣鸣很忙集团全国门店数位居零食连锁行业第一。 在此之前&#xff0c;尽管零食很…

Photoshop 2024 mac/win版:探索图像处理的全新境界

Photoshop 2024是Adobe推出的最新图像处理与设计软件&#xff0c;它在继承了前作所有优秀特性的基础上&#xff0c;实现了多个方面的质的飞跃。这款软件凭借其卓越的图像处理性能、丰富的创意工具以及精确的选区编辑功能&#xff0c;成为了图像处理领域的佼佼者。 Photoshop 2…

Spring的循环依赖

循环依赖概述 循环依赖其实也很好理解&#xff0c;可以将这个词拆分成两部分&#xff0c;一个是循环&#xff0c;一个是依赖。循环&#xff0c;顾名思义就是指形成了一个闭合环路&#xff0c;也就是闭环。依赖就是指某个事件的发生要依赖另一个事件。 在Spring中的循环依赖就…

CTFHUB-SQL注入-Cookie注入

由于本关是cookie注入&#xff0c;就不浪费时间判断注入了&#xff0c;在该页面使用 burp工具 抓包&#xff0c;修改cookie后面&#xff0c;加上SQL语句&#xff0c;关掉burp抓包&#xff0c;就可以在题目页面显示结果了 判断字段数量 发现字段数量是2列 使用id-1 union sele…

NewStarCTF_RE(week1,2)

[NewStarCTF 2023 公开赛道]easy_RE ida 可能会把 一个数组或字符串拆开&#xff0c;可以通过计算地址&#xff0c;知道是一起的 也有的会藏在汇编窗口 Segments IDA的Segments窗口 &#xff1a;shiftf7 https://www.cnblogs.com/sch01ar/p/9477697.html ida 各种窗口也是需要…