LeetCode 236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
提示:
1、树中节点数目在范围 [2, 105] 内。
2、-109 <= Node.val <= 109
3、所有 Node.val 互不相同 。
4、p != q
5、p 和 q 均存在于给定的二叉树中。
思路:
本题使用递归,判断当前结点的左右树是否同时包含p,q,若左树同时包含p,q,左树的左树,不同时包含,那么当前节点的左节点就是最近的公共祖先
代码:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null){return null;}if(root==p||root==q){return root;}TreeNode leftTree=lowestCommonAncestor(root.left,p,q);TreeNode rightTree=lowestCommonAncestor(root.right,p,q);if(leftTree!=null&&rightTree!=null){return root;}if(leftTree!=null){return leftTree;}if(rightTree!=null){return rightTree;}return null;}
}
相关文章:
LeetCode 236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖…...
awk简单实例(持续更新中)
一 概述 awk命令是一种分析和处理文本文件的编程工具。它的功能非常强大,是Linux/Unix系统中最常用的过滤工具。 awk内建变量: NF 整个数据行(即$0)拥有的字段总数 NR 当前awk所处理的数据行的编号 $0 当前awk所处理的数据行 $1 数据行的第1个字段 $2 数…...
react动态路由组件的封装
react动态路由组件的封装 我这篇比较全面 首先下载包 npm i react-router-dom5 这里为什么要用5的版本为啥不用最新的,原因在于老版本跟新版本写法不一样 老版本 import { HashRouter, Route, Switch, Redirect } from react-router-dom;render() {return (<Ha…...
Vue项目中引入高德地图步骤详解
高德地图API官网:高德开放平台 | 高德地图API。 目录 一、案例效果 二、开发准备 1. 注册高德开放平台账号 2. 创建应用添加 key 值 三、项目中使用地图组件 1. npm 获取高德地图 API 2.在项目中新建 MapContainer.vue 文件,用作地图组件。 3.在…...
软件测试用例篇(2)
功能测试界面测试兼容性测试安全测试易用性测试性能测试 针对有需求的案例来设计测试用例:邮箱注册,部分测试用例 https://zay1xofb7z6.feishu.cn/mindnotes/bmncnKD5Ak6GSZl3PRlWDgF9z3g#mindmap 一)等价类: 场景需求:姓名长度是6-200位,那么如何进行设…...
leetcode题解-27. Remove Element
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面…...
【fly-iot飞凡物联】(4):在linux系统上搭建arduino环境,可以使用离线包,导入到arduino上即可。
目录前言1,关于2,然后就可以找到ESP32,ESP8266的主版3,方法2,github下载,然后手动添加到ide中吧4,总结前言 本文的原文连接是: https://blog.csdn.net/freewebsys/article/details/108971807 未…...
java实例解析类图中【关联、组合和聚合】的区别
总目录链接==>> AutoSAR入门和实战系列总目录 文章目录 聚合Composition聚合与组合的区别关联是两个独立类之间的关系,它通过它们的对象建立关联。关联可以是一对一、一对多、多对一、多对多。在面向对象的编程中,一个对象与另一个对象通信以使用该对象提供的功能和服…...
基于m-p条件查询代码生成
目录 起因 演示 使用 0.自定义注解 1.定义一个dto的条件查询类 2.调用主程序 效果图 小结 代码 注解 Dto类 完整代码 起因 最近两天一直写后台管理统计的增删改查(很少写增删改查,所以不是很熟练),几乎每个表都要涉及到条件查询的业务…...
【LeetCode】带环链表两道题
第一题:环形链表 问题介绍 给你一个链表的头节点head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos 来表示链表…...
CSS奇思妙想之-利用CSS裁剪(clip-path)完成各种图形
在日常开发当中,如果想要开发多边形,一般都需要多个盒子或者伪元素的帮助,有没有一直办法能只使用一个盒子实现呢? 有的:css裁剪 clip-path介绍 css裁剪(clip-path)这个属性平时率非常低。但是…...
力扣每日一题刷题总结:哈希表篇
剑指 Offer II 033.变位词组 Medium 哈希表 变位词 2023/3/3 给定一个字符串数组 strs ,将 变位词 组合在一起。 可以按任意顺序返回结果列表。 注意:若两个字符串中每个字符出现的次数都相同,则称它们互为变位词。 示例: 示例 1:…...
【Redis】redis大key和大value的危害,如何处理?
前序 还记得上次和同事一起去面试候选人时,同事提了一个问题:Redis的大key有什么危害?当时候选人主要作答的角度是一个key的value较大时的情况,比如: 内存不均:单value较大时,可能会导致节点之…...
Spring Boot:实现MyBatis动态创建表
在有些应用场景中,我们会有需要动态创建和操作表的需求。 比如因为单表数据存储量太大而采取分表存储的情况,又或者是按日期生成日志表存储系统日志等等。这个时候就需要我们动态的生成和操作数据库表了。 而我们都知道,以往我们使用MyBati…...
SpringBoot+Seata在多数据源和feign中的简单使用
SpringBootSeata简单使用 目录seata执行过程安装seata下载seata使用自定义配置文件,NACOS为注册中心结合springboot实现AT模式1.多数据源引入依赖bootstrap.yml配置在使用的方法上用GlobalTransactional注解调用接口正常时调用接口报错时回滚2.配合feignseata优缺点seata执行过…...
计算机网络中的原码、反码、补码
写在前面 原码、反码、补码是计算机组成原理中的概念,是计算机网络的基础知识之一。这些概念是为了处理二进制数的符号位而引入的,常用于计算机中的整数运算,也常用于数据存储和传输等领域。因此,了解和掌握这些概念对于理解计算机…...
七、Bean的实例化方式
Spring为Bean提供了多种实例化方式,通常包括4种方式。(也就是说在Spring中为Bean对象的创建准备了多种方案,目的是:更加灵活) 第一种:通过构造方法实例化第二种:通过简单工厂模式实例化第三种&…...
Windows程序员学习Linux环境下VI(VIM)编辑器的使用方法
我是荔园微风,作为一名在IT界整整25年的老兵,今天我们来重新审视一下Windows程序员如何学习Linux环境知识。由于很多程序在Windows环境下开发好后,还要部署到Linux服务器上去,所以作为Windows程序员有必要学习Linux环境的知识。VI…...
react入门篇
react入门篇前言一、目标二、项目环境三、实现过程(干货满满💥💥💥)1.创建react项目2.arco design UI库3.路由模块化4. 状态管理zustand5. axios6. 路由守卫前言 提示:这里可以添加本文要记录的大概内容&a…...
阿赵的MaxScript学习笔记分享九《可编辑多面体的操作》
大家好,我是阿赵。这是MaxScript学习笔记分享的第九篇,可编辑多面体的操作。不知不觉写了这么多篇了,应该还有几篇就写完了。自己给自己加一下油。 在3DsMax里面如果需要建模,一般使用到的塌陷方式有3种,可编辑的网格、…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
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日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
