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

【数据结构】二叉树篇|超清晰图解和详解:二叉树的最近公共祖先

在这里插入图片描述

  • 博主简介:努力学习的22级计算机科学与技术本科生一枚🌸
  • 博主主页: @是瑶瑶子啦
  • 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏

目录

  • 一、题目
  • 二、题解
  • 三、代码

一、题目

🔗236. 二叉树的最近公共祖先

在这里插入图片描述

二、题解

在这里插入图片描述注意:祖先是包括自身的!

  • 🍊首先要明白,当root为p,q的最近祖先节点,只有下面3种情况:

    1. p,q在root分别存在于root的左右子树中(异侧)——>root即为最近祖先节点
    2. p, q均在root的左侧——>p/q即为最近祖先节点
    3. p, q均在root的右侧——>同理
    在这里插入图片描述

  • 🍊递归函数的定义public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)在以root为根节点的树中找并且返回p和q的最近的祖先节点。
    1.终止条件:

    • root == null;return null
    • root = = p 或者root = = q,直接返回p/q

    2.递推工作:(到这里说明此时p和q要么在此次递归的root的同侧或者异侧)left 用于记录在左侧进行寻找公共祖先(这里的递归函数作用就是单纯找q/p节点并且找到就返回的作用了,当然你可以另外写一个找节点的函数,但是没必要,因为定义的递归函数本身就能实现这个功能),right同理

  1. left和right均为null,说明root的左右都没有p,q,那就不存在公共节点,返回Null(有点扯,按理来说,p,q肯定是存在的,但是特判一下也不亏)

  2. left和right均不空,说明在此时递归情况是:p,q在root异侧,那么直接返回root即可
    在这里插入图片描述

    3. ⭐left不为空,right为空;right不为空,left为空。直接将不为空的那个返回即可!此时不为空的left/right指向的就是最近祖先节点。 在这里插入图片描述

三、代码

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q){return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left != null && right !=null){return root;}else if(left == null){return right;}else if(right == null){return left;}else{return null;}}

💐若有不懂的地方,欢迎随时在评论区or私信找瑶瑶子交流讨论🌺

在这里插入图片描述

  • Java岛冒险记【从小白到大佬之路】

  • LeetCode每日一题–进击大厂

  • Go语言核心编程

  • 算法

相关文章:

【数据结构】二叉树篇|超清晰图解和详解:二叉树的最近公共祖先

博主简介:努力学习的22级计算机科学与技术本科生一枚🌸博主主页: 是瑶瑶子啦每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏 目录 一、题目二、题解三、代码 一、题目 …...

android ndk clang交叉编译ffmpeg动态库踩坑

1.ffmpeg默认使用gcc编译,在android上无法使用,否则各种报错,所以要用ndk的clang编译 2.下载ffmpeg源码 修改configure文件,增加命令 cross_prefix_clang 修改以下命令 cc_default"${cross_prefix}${cc_default}" cxx…...

简单记录牛客top101算法题(初级题C语言实现)BM24 二叉树的中序遍历 BM28 二叉树的最大深度 BM29 二叉树中和为某一值的路径

1. BM24 二叉树的中序/后续遍历 要求:给定一个二叉树的根节点root,返回它的中序遍历结果。                          输入:{1,2,#,#,3} 返回值:[2,3,1]1.1 自己的整体思路(与二叉树的前序遍…...

前后端分离------后端创建笔记(05)用户列表查询接口(上)

本文章转载于【SpringBootVue】全网最简单但实用的前后端分离项目实战笔记 - 前端_大菜007的博客-CSDN博客 仅用于学习和讨论,如有侵权请联系 源码:https://gitee.com/green_vegetables/x-admin-project.git 素材:https://pan.baidu.com/s/…...

性能测试|App性能测试需要关注的指标

一、Android客户端性能测试常见指标: 1、内存 2、CPU 3、流量 4、电量 5、启动速度 6、滑动速度、界面切换速度 7、与服务器交互的网络速度 二、预期标准指定原则 1、分析竞争对手的产品,所有指标要强于竞品 2、产品经理给出的预期性能指标数据…...

Termux SFTP 进行远程文件传输

文章目录 1. 安装openSSH2. 安装cpolar3. 远程SFTP连接配置4. 远程SFTP访问4. 配置固定远程连接地址 SFTP(SSH File Transfer Protocol)是一种基于SSH(Secure Shell)安全协议的文件传输协议。与FTP协议相比,SFTP使用了…...

Sqlite3简介

SQLite3 简介 SQLite3 是一种轻量级的嵌入式数据库引擎,被广泛应用于各种应用程序中,包括移动设备、桌面应用程序和嵌入式系统。它以其简单、高效和零配置的特点而受到开发者的喜爱。 以下是 SQLite3 的一些重要特点: 嵌入式数据库引擎&…...

K8S调度

K8S调度 一、List-Watch 机制 controller-manager、scheduler、kubelet 通过 List-Watch 机制监听 apiserver 发出的事件,apiserver 通过 List-Watch 机制监听 etcd 发出的事件1.scheduler 的调度策略 预选策略/预算策略:通过调度算法过滤掉不满足条件…...

vue+element多层表单校验prop和rules

核心点:外层循环是item和index,内层循环是item2和index2 如果都是定义的同一个属性名 外层循环得写:prop"block.index.numerical" 同理内层循环就得写:prop"objectSpecs. index2 .numerical" 校验函数方法 :rules"getRules(it…...

Dubbo 核心概念和架构

以上是 Dubbo 的工作原理图,从抽象架构上分为两层:服务治理抽象控制面 和 Dubbo 数据面 。 服务治理控制面。服务治理控制面不是特指如注册中心类的单个具体组件,而是对 Dubbo 治理体系的抽象表达。控制面包含协调服务发现的注册中心、流量管…...

【数据结构OJ题】反转链表

原题链接:https://leetcode.cn/problems/reverse-linked-list/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 方法一:三指针翻转法 使用三个结构体指针n1,n2,n3,原地修改结点…...

Java8 Stream 之groupingBy 分组讲解

本文主要讲解&#xff1a;Java 8 Stream之Collectors.groupingBy()分组示例 Collectors.groupingBy() 分组之常见用法 功能代码: /** * 使用java8 stream groupingBy操作,按城市分组list */ public void groupingByCity() { Map<String, List<Em…...

优哲SSD大文件写性能测试

SDD磁盘性能测试&#xff1a; 空盘&#xff1a; 大文件读&#xff0c;写&#xff0c;读写&#xff08;4/6&#xff09;性能测试&#xff0c;删除性能测试&#xff0c;N进程&#xff0c;N线程 小文件读&#xff0c;写&#xff0c;读写&#xff08;4/6&#xff09;性能测试&am…...

Python基础教程: json序列化详细用法介绍

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 Python内置的json模块提供了非常完善的对象到JSON格式的转换。 废话不多说&#xff0c;我们先看看如何把Python对象变成一个JSON&#xff1a; d dict(nameKaven, age17, sexMale) print(json.dumps(d)) # {"na…...

一张图看懂 USDT三种类型地址 Omni、ERC20、TRC20的区别

USDT是当前实用最广泛&#xff0c;市值最高的稳定币&#xff0c;它是中心化的公司Tether发行的。在今年的4月17日之前&#xff0c;市场上存在着2种不同类型的USDT。4月17日又多了一种波场TRC20协议发行的USDT&#xff0c;它们各自有什么区别呢?哪个转账最快到账&#xff1f;哪…...

SegFormer之模型训练

单卡训练&#xff0c;所有配置文件里的【SyncBN】改为【BN】 启动训练 &#xff08;1&#xff09;终端直接运行 python tools/train.py local_configs/segformer/B1/segformer.b1.512x512.ade.160k.py &#xff08;2&#xff09;在编辑器中运行 在 [config] 前面加上’–‘将…...

Azure资源命名和标记决策指南

参考 azure创建虚拟机在虚拟机中选择编辑标签&#xff0c;并添加标记&#xff0c;点击应用 3.到主页中转到所有资源 4. 添加筛选器并应用 5.查看结果&#xff0c;筛选根据给服务器定义的标签筛选出结果。 参考链接: https://learn.microsoft.com/zh-cn/azure/cloud-adoption…...

【在一个升序数组中插入一个数仍升序输出】

在一个升序数组中插入一个数仍升序输出 题目举例&#xff1a; 有一个升序数组nums&#xff0c;给一个数字data&#xff0c;将data插入数组nums中仍旧保证nums升序&#xff0c;返回数组中有效元素个数。 比如&#xff1a;nums[100] {1, 2, 3, 5, 6, 7, 8, 9} size 8 data 4 …...

图像去雨、去雪、去雾论文学习记录

All_in_One_Bad_Weather_Removal_Using_Architectural_Search 这篇论文发表于CVPR2020&#xff0c;提出一种可以应对多种恶劣天气的去噪模型&#xff0c;可以同时进行去雨、去雪、去雾操作。但该部分代码似乎没有开源。 提出的问题&#xff1a; 当下的模型只能针对一种恶劣天气…...

YARN框架和其工作原理流程介绍

目录 一、YARN简介 二、YARN的由来 三、YARN的基本设计思想 四、YARN 的基本架构 4.1 基本架构图 4.2 基本组件介绍 4.2.1 ResourceManager 4.2.1.1 任务调度器(Resource Scheduler) 4.2.1.2 应用程序管理器&#xff08;Applications Manager&#xff09; 4.2.1.3 其他…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...