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 为不同节点且均存在于给定的二叉搜索树中。

 //本题,由于是找到 == q,p的parent,所以找到就返回,而不用遍历整棵树,所以,采用return

。递归函数有返回值,那就是搜索一条边,符合就立即返回。但是有返回值(搜索一条边),也要看,是搜索一条边还是整棵树。很明显二叉搜索树,不需要搜索整棵树。而二叉树需要搜索整棵树,因为没有二叉搜索树的特性,导致需要右子树的返回值做判断。

class Solution {
public:TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode* q){if(!root) return root;//中序if(root->val > p->val && root->val > q->val){TreeNode* left = NULL;left = dfs(root->left,p,q);if(left) return left;}else if(root->val < p->val && root->val < q->val){ TreeNode* right = NULL;right = dfs(root->right,p,q);if(right) return right; //由于是找到符合的值就返回,所以是遍历一条边,而不是整棵树}return root;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//dfsif(!root) return root; return dfs(root,p,q);}
};
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//迭代TreeNode* cur = root;while(cur){if(cur->val < q->val && cur->val < p->val){cur = cur->right;}else if(cur->val > q->val && cur->val > p->val){cur = cur->left;}else{return cur;}}return cur;}
};

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

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

相关文章

git 同时配置 gitee github

git 同时配置 gitee github 1、 删除C:\Users\dell\.ssh目录。 在任意目录右击——》Git Bash Here&#xff0c;打开Git Bash窗口&#xff0c;下方命令在Git Bash窗口输入。 2、添加git全局范围的用户名和邮箱 git config --global user.email "609612189qq.com" …

秋日氛围 VoxEdit 大赛

将您的创造力提升到一个新的水平。在这个美妙的季节性 VoxEdit 比赛中释放您惊人的体素设计技能。 下载 VoxEdit 开始创作吧&#xff01; 主题&#xff1a;秋天的颜色无处不在。红色、黄色和橙色。南瓜、树叶和温暖舒适的毛衣。创造一个秋天相关的资产。无论是一个穿着秋季衣…

Windows下载AOSP

关于repo repo只是谷歌做的&#xff0c;方便下载安卓源码的工具&#xff0c;本质上是对下载清单进行批量处理&#xff0c;然后使用git克隆。 在windows上下载源码只需要自己处理即可。 具体做法 首先使用git克隆安卓源码清单 git clone https://mirrors.tuna.tsinghua.edu.…

产品经理需要掌握哪些产品专业知识?

作为产品经理&#xff0c;最重要的是洞察客户的需求、理解客户的需求、掌握客户的需求&#xff0c;所以&#xff0c;第一件事情就是要有清晰的战略方向&#xff0c;我们到底梦想是什么&#xff1f;要做什么&#xff1f;能做什么&#xff1f;在哪儿做&#xff1f;谁负责去做&…

为什么mac上有的软件删除不掉?

对于Mac用户来说&#xff0c;软件卸载通常是一个相对简单的过程。然而&#xff0c;有时你可能会发现某些软件似乎“顽固不化”&#xff0c;即使按照常规方式尝试卸载&#xff0c;也依然存在于你的电脑上。这到底是为什么呢&#xff1f;本文将探讨这一问题的可能原因。 1.卸载失…

buuctf-[WUSTCTF2020]CV Maker 文件上传漏洞

打开环境 随便登录注册一下 进入到了profile.php 其他没有什么页面&#xff0c;只能更换头像上传文件&#xff0c;所以猜测是文件上传漏洞 上传一句话木马看看 <?php eval($_POST[a]);?>回显 搜索一下 添加文件头GIF89a。上传php文件 查看页面源代码&#xff0c;看…

求推荐好用的可视化大屏软件?强推奥威BI

在博览中心、会议中心、监控中心等场合下&#xff0c;经常看到很多炫酷的企业可视化大屏&#xff0c;将复杂的企业数据可视化展现&#xff0c;高大上、实用性一个不缺。那&#xff0c;可视化大屏做得好的软件有哪些&#xff1f;首推奥威BI软件。 奥威BI软件&#xff1a;零编程…

数据结构与算法(持续更新)

线性表 单链表 单链表的定义 由于顺序表的插入删除操作需要移动大量的元素&#xff0c;影响了运行效率&#xff0c;因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素&#xff0c;不需要使用地址连续的存储单元&#xff0c;因此它…

Flink---12、状态后端(HashMapStateBackend/RocksDB)、如何选择正确的状态后端

星光下的赶路人star的个人主页 大鹏一日同风起&#xff0c;扶摇直上九万里 文章目录 1、状态后端&#xff08;State Backends&#xff09;1.1 状态后端的分类&#xff08;HashMapStateBackend/RocksDB&#xff09;1.2 如何选择正确的状态后端1.3 状态后端的配置 1、状态后端&am…

APP自动化之Poco框架

今天给大家介绍一款自动化测试框架Poco&#xff0c;其脚本写法非常简洁、高效&#xff0c;其元素定位器效率更快&#xff0c;其本质基于python的第三方库&#xff0c;调试起来也会非常方便&#xff0c;能够很好的提升自动化测试效率&#xff0c;节省时间。 (一&#xff09;背景…

Zabbix 监控系统安装和部署

Zabbix 监控系统安装和部署 一、zabbix 是什么&#xff1f;1.1、zabbix 监控原理&#xff08;重点&#xff09;1.2、Zabbix 6.0 新特性1.3、Zabbix 6.0 功能组件1.4、数据库1.5、Web 界面1.6、Zabbix Agent1.7、Zabbix Proxy1.8、Java Gateway 二、部署Zabbix 6.02.1、 解决 za…

SQL监控工具

什么是 SQL 监控 SQL 监视是跟踪和分析整个 MSSQL 生态系统的过程&#xff0c;以识别性能问题并防止依赖数据库的应用程序变慢和/或遇到中断&#xff0c;它有助于获取有关 SQL 服务器的数据库会话、查询、作业、CPU 和内存资源、群集、配置和可用性组的信息。 为什么 MSSQL 监…

Redis-缓存穿透,缓存击穿,缓存雪崩

缓存穿透&#xff0c;缓存击穿&#xff0c;缓存雪崩 缓存穿透处理方案解决方案1 缓存空数据解决方案2 布隆过滤器 缓存击穿处理方案解决方案 1 互斥锁解决方案2 逻辑过期 缓存雪崩处理方案解决方案 1 给不同的key的过期时间设置添加一个随机值&#xff0c;降低同一个时段大量ke…

cv2.split函数与cv2.merge函数

split函数用于图像BGR通道的分离 merge函数用于可将分开的图像通道合并到一起 1.split函数的使用 这是原图&#xff0c;我们使用split函数对其三个通道进行分离。 注意&#xff1a;split函数分离通道的顺序是B、G、R。 以下方法是将三个通道的值都设置为与某一个通道相同。…

基于双二阶广义积分器的三相锁相环(DSOGI-PLL)Simulink仿真

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

虚拟机模拟部署服务器

1、下载安装vmware 15 &#xff08;win7最高支持版&#xff09; 2、下载安装CentOS 配置2核2g&#xff08;最少&#xff09;磁盘100g&#xff08;不会实际占有&#xff09;选择时区配置分区 https://blog.csdn.net/qq_35363507/article/details/127390889 &#xff08;/boot …

Java 华为真题-小朋友分班

需求&#xff1a; 题目描述 幼儿园两个班的小朋友在排队时混在了一起&#xff0c;每位小朋友都知道自己是否与前面一位小朋友同班&#xff0c;请你帮忙把同班的小朋友找出来小朋友的编号是整数&#xff0c;与前一位小朋友同班用Y表示&#xff0c;不同班用N表示学生序号范围(0&…

旁注、越权、跨库、CDN相关

旁注原理 在同一服务器上有多个站点&#xff0c;我们要攻击的这个站点假设没有漏洞&#xff0c;我们可以攻击服务器上的任意一个站点&#xff0c;这个就是旁注 多端口需要知道IP 可以用尖刀&#xff0c;fscan,goby 探测 IP逆向查询&#xff08;知道域名&#xff09; 可通过pin…

Java版 招投标系统简介 招投标系统源码 java招投标系统 招投标系统功能设计

功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外部供…

基于or-tools的人员排班问题建模求解(JavaAPI)

使用Java调用or-tools实现了阿里mindopt求解器的案例&#xff08;https://opt.aliyun.com/platform/case&#xff09;人员排班问题。 这里写目录标题 人员排班问题问题描述数学建模编程求解&#xff08;ortoolsJavaAPI&#xff09;求解结果 人员排班问题 随着现在产业的发展&…