LeetCode235. 二叉搜索树的最近公共祖先

news/2024/11/2 5:00:35/

235. 二叉搜索树的最近公共祖先

文章目录

      • [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]

img

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

二、题解

方法一:递归

我们需要充分利用二叉搜索树的性质,即左子树的所有节点值都小于根节点值,右子树的所有节点值都大于根节点值。这个性质可以帮助我们有效地缩小搜索范围。

算法思路

  1. 首先,我们要考虑一种简单情况:如果根节点的值大于节点 p 和 q 的值,那么说明 p 和 q 位于根节点的左子树中,因为左子树的所有节点值都小于根节点值。我们可以在根节点的左子树上继续搜索 p 和 q 的最近公共祖先。

  2. 同样,如果根节点的值小于节点 p 和 q 的值,那么说明 p 和 q 位于根节点的右子树中,因为右子树的所有节点值都大于根节点值。我们可以在根节点的右子树上继续搜索 p 和 q 的最近公共祖先。

  3. 但是,如果根节点的值介于节点 p 和 q 的值之间,或者根节点的值等于其中一个节点的值,那么说明 p 和 q 分别位于根节点的左右子树中,此时根节点就是它们的最近公共祖先。

  4. 我们可以利用递归来实现这个过程,根据上述的思路,递归搜索左子树和右子树,最终找到最近公共祖先。

具体实现

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return nullptr;if (root->val > p->val && root->val > q->val) {TreeNode* left = lowestCommonAncestor(root->left, p, q);return left;}if (root->val < p->val && root->val < q->val) {TreeNode* right = lowestCommonAncestor(root->right, p, q);return right;}return root;}
};

算法分析

时间复杂度

  • 在每个递归步骤中,我们都会根据节点的值来决定是继续在左子树搜索还是在右子树搜索,所以每次递归都会剔除一半的节点。因此,算法的时间复杂度为 O(log N),其中 N 是树中节点的总数。

空间复杂度

  • 递归调用栈的最大深度取决于树的高度,对于平衡的二叉搜索树,空间复杂度为 O(log N);对于不平衡的树,最坏情况下的空间复杂度为 O(N),其中 N 是树中节点的总数。
方法二:迭代

简单来说,就是把上面的递归思路用迭代方式写一遍:

/*** 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:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(root){if(root->val > p->val && root->val > q->val){root = root->left;}else if(root->val < p->val && root->val < q->val){root = root->right;}else{return root;}}return root;}
};

http://www.ppmy.cn/news/1037838.html

相关文章

ZooKeeper的应用场景(集群管理、Master选举)

5 集群管理 随着分布式系统规模的日益扩大&#xff0c;集群中的机器规模也随之变大&#xff0c;因此&#xff0c;如何更好地进行集群管理也显得越来越重要了。 所谓集群管理&#xff0c;包括集群监控与集群控制两大块&#xff0c;前者侧重对集群运行时状态的收集&#xff0c;后…

uniapp 上传比较大的视频文件就超时

uni.uploadFile&#xff0c;上传超过10兆左右的文件就报错err&#xff1a;uploadFile:fail timeout&#xff0c;超时 解决&#xff1a; 在manifest.json文件中做超时配置 uni.uploadFile({url: this.action,method: "POST",header: {Authorization: uni.getStorage…

IDEA部署配置Maven项目教程,IDEA配置Tomcat(2019.3.3)(2023.1.3)

我们往往会用到多版本的IDEA进行一个Maven项目配置部署&#xff0c;还有tomcat的配置&#xff0c;这里就有你需要的&#xff0c;有低版本的&#xff0c;也有高版本的&#xff0c;根据自己的情况来进行一个操作 一、前言 当涉及到软件开发和项目管理时&#xff0c;使用一个可靠的…

数字图像处理-AWB跳变

1、自动白平衡&#xff08;AWB&#xff09;算法是相机中常用的图像处理技术&#xff0c;它能够自动调整图像中的白平衡&#xff0c;使得图像中的颜色更加真实、自然。然而&#xff0c;在实际应用中&#xff0c;AWB算法也存在着一些问题&#xff0c;例如AWB跳变&#xff08;Whit…

LVS-DR模式

目录 1、概述 2、LVS-DR模式的工作原理&#xff1a; 3、在LVS-DR模式下&#xff0c;数据包的流向分析如下&#xff1a; 4、LVS-DR是一种用于构建高可用性负载均衡集群的技术模式。LVS-DR模式具有以下特点&#xff1a; 5、LVS-DR中的ARP问题 6、配置LVS-DR需要以下几个关键…

Kubernetes网络组件详解

目录 1、Kubernetes网络组件 1.1、Flannel网络组件 1.2、Calico 网络插件 2、环境准备 2.1、主机初始化配置 2.2、部署docker环境 3、部署kubernetes集群 3.1、组件介绍 3.2、配置阿里云yum源 3.3、安装kubelet kubeadm kubectl 3.4、配置init-config.yaml 3.6、安装…

web连接桌面打开gptmap

一&#xff1a;环境配置 需要的材料&#xff1a; python-3.10.4 我使用的是这个版本的&#xff0c;3.8.10 该版本和以下版本组件组合&#xff0c;验证过能正常运行&#xff08;python 3.6.8测试异常&#xff09; websockify 该项目有python版本和node js版本 noVNC 形式的app…

[MySQL] — 数据类型和表的约束

目录 数据类型 数据类型分类 数值类型 tinyint类型 bit类型 小数类型 float decimal 字符串类型 char varchar char和varchar的区别 日期和时间类型 enum 和 set 表的约束 空属性 默认值 列描述 zeorfill 主键 创建表时在字段上指定主键 删除主键&#xff1a; 追…