二叉搜索树题目:二叉搜索树的最近公共祖先

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:二叉搜索树的最近公共祖先

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

难度

3 级

题目描述

要求

给定一个二叉搜索树,找到该树中两个指定结点的最近公共祖先。

最近公共祖先的定义为:两个结点 p \texttt{p} p q \texttt{q} q 的最近公共祖先是满足 p \texttt{p} p q \texttt{q} q 都是其后代的最低的结点 T \texttt{T} T(一个结点也可以是它自己的祖先)。

示例

示例 1:

示例 1

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 \texttt{root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8} root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 \texttt{6} 6
解释:结点 2 \texttt{2} 2 和结点 8 \texttt{8} 8 的最近公共祖先是结点 6 \texttt{6} 6

示例 2:

示例 2

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 \texttt{root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4} root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2 \texttt{2} 2
解释:结点 2 \texttt{2} 2 和结点 4 \texttt{4} 4 的最近公共祖先是结点 2 \texttt{2} 2。因为根据定义最近公共祖先结点可以为结点本身。

示例 3:

输入: root = [2,1], p = 2, q = 1 \texttt{root = [2,1], p = 2, q = 1} root = [2,1], p = 2, q = 1
输出: 2 \texttt{2} 2

数据范围

  • 树中结点数目在范围 [2, 10 5 ] \texttt{[2, 10}^\texttt{5}\texttt{]} [2, 105]
  • -10 9 ≤ Node.val ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{Node.val} \le \texttt{10}^\texttt{9} -109Node.val109
  • 所有 Node.val \texttt{Node.val} Node.val 各不相同
  • p ≠ q \texttt{p} \ne \texttt{q} p=q
  • p \texttt{p} p q \texttt{q} q 均存在于给定的二叉搜索树中

解法一

思路和算法

如果结点 p p p q q q 之间的关系是祖先和后代的关系,则其中的祖先即为最近公共祖先。如果结点 p p p q q q 之间的关系不是祖先和后代的关系,则结点 p p p q q q 分别在最近公共祖先的两个子树中。

对于二叉搜索树中的任意结点,其左子树中的结点值都小于当前结点值,其右子树中的结点值都大于当前结点值。首先比较根结点值和结点 p p p q q q 的结点值,缩小寻找最近公共祖先的范围。

  • 如果根结点值比结点 p p p q q q 的结点值都大,则结点 p p p q q q 都在根结点的左子树中,因此根结点的左子结点一定是结点 p p p q q q 的公共祖先,应该在根结点的左子树中寻找最近公共祖先。

  • 如果根结点值比结点 p p p q q q 的结点值都小,则结点 p p p q q q 都在根结点的右子树中,因此根结点的右子结点一定是结点 p p p q q q 的公共祖先,应该在根结点的右子树中寻找最近公共祖先。

  • 如果根结点值介于结点 p p p 和结点 q q q 的结点值之间(可以等于其中的一个结点值),则根结点的任何一个子结点都不可能是结点 p p p q q q 的公共祖先,因此根结点是结点 p p p q q q 的最近公共祖先。

上述过程是一个递归的过程。递归的终止条件是当前结点值介于结点 p p p 和结点 q q q 的结点值之间,此时当前结点是结点 p p p q q q 的最近公共祖先,返回当前结点。对于其余情况,定位到最近公共祖先所在的子树,对该子树调用递归。

由于结点 p p p q q q 都存在于给定的二叉搜索树中,因此最近公共祖先一定存在。

代码

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {int maxVal = Math.max(p.val, q.val);int minVal = Math.min(p.val, q.val);if (root.val <= maxVal && root.val >= minVal) {return root;}return root.val > maxVal ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。时间复杂度取决于二叉搜索树的高度,最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉搜索树的高度,最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

递归实现可以改成迭代实现。从根结点开始搜索,如果当前结点值结点值比结点 p p p q q q 的结点值都大或者都小,则执行如下操作,直到当前结点值介于结点 p p p 和结点 q q q 的结点值之间。

  • 如果当前结点值比结点 p p p q q q 的结点值都大,则结点 p p p q q q 都在当前结点的左子树中,因此将当前结点移动到左子结点。

  • 如果当前结点值比结点 p p p q q q 的结点值都小,则结点 p p p q q q 都在当前结点的右子树中,因此将当前结点移动到右子结点。

搜索结束时,当前结点为结点 p p p q q q 的最近公共祖先,返回当前结点。

由于结点 p p p q q q 都存在于给定的二叉搜索树中,因此最近公共祖先一定存在。

代码

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {int maxVal = Math.max(p.val, q.val);int minVal = Math.min(p.val, q.val);TreeNode node = root;while (node.val > maxVal || node.val < minVal) {if (node.val > maxVal) {node = node.left;} else {node = node.right;}}return node;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索树的结点数。时间复杂度取决于二叉搜索树的高度,最坏情况下二叉搜索树的高度是 O ( n ) O(n) O(n)

  • 空间复杂度: O ( 1 ) O(1) O(1)

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

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

相关文章

机器学习中的有监督学习和无监督学习

有监督学习 简单来说&#xff0c;就是人教会计算机学会做一件事。 给算法一个数据集&#xff0c;其中数据集中包含了正确答案&#xff0c;根据这个数据集&#xff0c;可以对额外的数据希望得到一个正确判断&#xff08;详见下面的例子&#xff09; 回归问题 例如现在有一个…

数模.matlab画图

一、mesh函数 上图是平常用到的方式 例题&#xff1a; 上图的meshgrid函数相当于上上图的前三个指令&#xff08;temp&#xff0c;x,y&#xff09; mash函数&#xff1a; mashc函数&#xff1a; mashz函数&#xff1a; 上图subplot函数的作用是将下标为index的图片放到对应的x&…

[技术杂谈]如何下载vscode历史版本

网站模板&#xff1a; https://code.visualstudio.com/updates/v1_85 如果你想下载1.84系列可以访问https://code.visualstudio.com/updates/v1_84​​​​​​ 然后看到&#xff1a; 选择对应版本下载即可&#xff0c;我是windows x64系统选择x64即可开始下载

C++杂选

#include <iostream> #include <regex>using namespace std;int main() { //它声明了一个 string 类型的变量 input&#xff0c;用于存储输入的字符串。然后使用 getline() 函数从标准输入中读取一行输入&#xff0c;并将其存储在 input 变量中。string input;getl…

Linux openKylin(开放麒麟)系统SSH服务安装配置与公网远程连接

文章目录 前言1. 安装SSH服务2. 本地SSH连接测试3. openKylin安装Cpolar4. 配置 SSH公网地址5. 公网远程SSH连接6. 固定SSH公网地址7. SSH固定地址连接8. 结语 前言 openKylin是中国首个基于Linux 的桌面操作系统开发者平台&#xff0c;通过开放操作系统源代码的方式&#xff…

pwn学习笔记(2)

pwn学习笔记&#xff08;2&#xff09; 1.三种常见的寄存器&#xff1a; ​ ax寄存器&#xff1a;通用寄存器&#xff0c;可用于存放多种数据 ​ bp寄存器&#xff1a;存放的是栈帧的栈底地址 ​ sp寄存器&#xff1a;存放的是栈顶的地址 2.栈帧与栈工作的简介&#xff1a…

【机器学习】基于集成学习的 Amazon 用户评论质量预测

实验六: 基于集成学习的 Amazon 用户评论质量预测 1 案例简介 ​ 随着电商平台的兴起&#xff0c;以及疫情的持续影响&#xff0c;线上购物在我们的日常生活中扮演着越来越重要的角色。在进行线上商品挑选时&#xff0c;评论往往是我们十分关注的一个方面。然而目前电商网站的…

vue前端+nodejs后端通信-简单demo

本文记录vue前端nodejs后端通讯最简单的方法&#xff0c;供广大网友最快速进入全栈开发。 技术架构 前端 vue axios 后端 nodejs express 一、前端部分-搭建VUE 项目 vue create Vnodenpm run serve 启动&#xff1b; 具体操作步骤&#xff0c;请自行百度&#xff0c;这里没…

ArcGIS学习(三)数据可视化

ArcGIS学习(三)数据可视化 1.矢量数据可视化 需要提前说明的是,在ArcGIS中,所有的可视化选项设置都是在“图层属性”对话框里面的“符号系统”中实现的。 对于矢量数据的可视化,主要有四种可视化方式: 按“要素”可视化按“类别”可视化按“数量”可视化按“图表”可视…

25.云原生ArgoCD高级之app of apps模式

文章目录 app of apps 模式介绍app如何管理apphelm方式管理kustomize方式管理 app of apps 模式介绍 通过一个app来管理其他app&#xff0c;当有多个项目要发布创建多个app比较麻烦&#xff0c;此时可以创建一个管理app&#xff0c;管理app创建后会创建其他app。比较适合项目环…

Linux--- vim详解

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 “学如逆水行舟&#xff0…

EF Core 的基本使用及常见的坑

EF Core 的基本使用及常见的坑 1. EF Core 是什么 简单来说&#xff0c;就是实现代码中的类到数据库中表的映射的一种方法。 宝啊&#xff0c;是不是觉得我才开篇就鬼话连篇。 举个例子&#xff0c;假设我们要创建一个名为employees的表&#xff0c;包含id、name、age和salar…

vue实现瀑布流

每个色块宽度一致&#xff0c;高度自适应 <!DOCTYPE html> <html><head><meta charset"utf-8"><meta http-equiv"X-UA-Compatible" content"IEedge,chrome1"><meta name"renderer" content"we…

STM32F407移植OpenHarmony笔记7

继上一篇笔记&#xff0c;成功启动了liteos_m内核&#xff0c;可以创建线程了&#xff0c;也能看到shell控制台了。 今天研究文件系统&#xff0c;让控制台相关文件命令如mkdir和ls能工作。 liteos_m内核支持fatfs和littlefs两个文件系统&#xff0c; fatfs适用于SD卡&#xff…

【C++】C++入门 — 类和对象初步介绍

类和对象 1 类的作用域2 类的实例化3 类对象模型4 this指针介绍&#xff1a;特性&#xff1a; Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;下一篇文章见&#xff01;&#xff01;&#xff01; 1 类的作用域 类定义了一个新的作用域&#xff0c;类的…

指针的深入理解(四)

这节主要讨论sizeof和strlen的区别&#xff0c;以及一些理解题。 sizeof 求的是对象的大小&#xff0c;深入理解一点就是&#xff1a;这个对象&#xff0c;他一定有一块对应的内存空间。求的就是这一块内存空间。 strlen 只能用来求字符串&#xff0c; 求取的是字符串的长度。…

QT 范例阅读:系统托盘 The System Tray Icon example

main.cpp QApplication app(argc, argv);//判断系统是否支持 系统托盘功能if (!QSystemTrayIcon::isSystemTrayAvailable()) {QMessageBox::critical(0, QObject::tr("Systray"),QObject::tr("I couldnt detect any system tray ""on this system.&qu…

【C++】开源:Windows图形库EasyX配置与使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍Windows图形库EasyX配置与使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#…

Linux进程信号(2)--信号的保存

目录 1.阻塞信号 1.1 信号其他相关常见概念 1.实际执行信号的处理动作称为信号递达(Delivery&#xff09; 2.信号从产生到递达之间的状态,称为信号未决(Pending)。 3.进程可以选择阻塞 (Block )某个信号。 1.2信号在内核中的表示 sigset_t 信号集操作函数 使用sigprocm…

nginx slice模块的使用和源码分析

文章目录 1. 为什么需要ngx_http_slice_module2. 配置指令3. 加载模块4. 源码分析4.1 指令分析4.2 模块初始化4.3 slice模块的上下文4.2 $slice_range字段值获取4.3 http header过滤处理4.4 http body过滤处理5 测试和验证 1. 为什么需要ngx_http_slice_module 顾名思义&#…