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

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 为不同节点且均存在于给定的二叉搜索树中。
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==NULL)return root;if(root->val<q->val&&root->val<p->val)return lowestCommonAncestor(root->right,p,q);if(root->val>q->val&&root->val>p->val)return lowestCommonAncestor(root->left,p,q);else return root;}
};

http://www.lryc.cn/news/168936.html

相关文章:

  • DETR:End-to-End Object Detection with Transformers
  • 如何从第一性原则的原理分解数学问题
  • 实现strstr函数
  • C语言练习题解析(2)
  • Element UI 表单验证规则动态失效问题
  • 多线程并发篇
  • pycharm-2023.1 closing project window stuck
  • tkinter编写的打开csdn程序
  • Vue3.2组件如何封装,以弹窗组件的封装为例
  • Vue知识系列(5)每天10个小知识点
  • Java基础题08——数组(查找下标所对应的值)
  • LinkedList 源码分析
  • 跑步锻炼(蓝桥杯)
  • 【SLAM】视觉SLAM简介
  • Visual Studio2019报错
  • ffplay源码解析-PacketQueue队列
  • Flowable主要API介绍
  • TensorFlow与pytorch特定版本虚拟环境的安装
  • 【SpringMVC】拦截器JSR303的使用
  • Java - LambdaQueryWrapper 的常用方法
  • Selenium常见问题解析
  • 【npm】npm私有库的使用-绑定
  • spring seccurity OAuth 2.0授权服务器工作流程
  • 【Tensorflow 2.12 电影推荐系统之排序模型】
  • ROS2-IRON Ubuntu-22.0 源码下载失败解决方法 vcs import --input
  • 百度SEO优化技巧大揭秘(百度SEO优化策略,提升网站排名)
  • JavaScript:二进制数组【笔记】
  • 华为云认证考试包含哪些内容?
  • 进程程序替换
  • 理解HTTPS/TLS/SSL(二)可视化TLS握手过程并解密加密数据