当前位置: 首页 > 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 其他…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...