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种,可编辑的网格、…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
