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

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

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

  • 题目-中等难度
  • 示例
  • 1. dfs

题目-中等难度

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

百度百科中最近公共祖先的定义为:“对于有根树 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

提示:

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

1. dfs

时间
52ms
击败 68.44%使用 Python 的用户
内存
24.04MB
击败 62.53%使用 Python 的用户

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""# 如果节点不存在或者节点是两个指定节点之一, 返回节点if not root or root == p or root ==q:return root# 左递归left = self.lowestCommonAncestor(root.left,p,q)# 右递归right = self.lowestCommonAncestor(root.right,p,q)# 如果左右都不为空, 说明指定节点存在于当前节点下if left and right:return root# 其他情况,只存在于当前节点的左子树或者右子树return left if left else right

相关文章:

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

236. 二叉树的最近公共祖先 题目-中等难度示例1. dfs 题目-中等难度 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p…...

Git常见问题:git pull 和 git pull --rebase二者区别

git pull 和 git pull --rebase 都是从远程仓库获取最新的更改并将其合并到本地分支。但它们之间的区别在于合并方式。以下是它们之间的主要区别&#xff1a; git pull&#xff1a; 当你执行 git pull 时&#xff0c;Git 会执行以下两个操作&#xff1a; git fetch&#xff…...

关于HarmonyOS元服务的主题演讲与合作签约

一、感言 坚持中&#xff0c;总会有很多意想不到的收获。 前几次参与HDC时更多的是观众、开发者、专家的身份&#xff0c;以参观、学习、交流为主。 通过几年的努力&#xff0c;和HarmonyOS功能成长&#xff0c;在2023年的HDC大会中&#xff0c;有了我的演讲&#xff0c;并带领…...

cache 学习

好文章&#xff1a; Cache的基本原理 - 知乎...

SSM - Springboot - MyBatis-Plus 全栈体系(六)

第二章 SpringFramework 四、SpringIoC 实践和应用 3. 基于 注解 方式管理 Bean 3.1 实验一&#xff1a;Bean 注解标记和扫描 (IoC) 3.1.1 注解理解 和 XML 配置文件一样&#xff0c;注解本身并不能执行&#xff0c;注解本身仅仅只是做一个标记&#xff0c;具体的功能是框…...

【Flutter】引入网络图片时,提示:Failed host lookup: ‘[图片host]‘

在使用 NetworkImage 组件加载外部图片时&#xff0c;提示 Failed host lookup: [图片host] 错误。 排查方向 1、清理缓存 解决方案&#xff1a; 尝试flutter clean清空缓存后重新安装依赖flutter pub get重新构建项目flutter create . 走完上述三个步骤后&#xff0c;再次…...

Python基础教程:索引和切片

前言 嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 索引&#xff08;下标&#xff09; 索引又称下标&#xff0c;用来表示可迭代对象中的某个元素的位置。 用正整数表示的索引值&#xff0c;从左向右定位&#xff0c;从 0 开始计数&#xff0c;如 0&#xff0c;1&#…...

JVM基础面试题

JDK、JRE、JVM的关系 JVM Java虚拟机&#xff0c;它只识别.class类型文件&#xff0c;它能将class文件中的字节码指令进行识别并调用操作系统向上的API完成动作。 JRE Java运行时环境。它主要包含两部分&#xff1a;Jvm的标准实现和Java的一些基本类库。相对于JVM来说,JRE多出来…...

蓝桥杯官网填空题(平方末尾)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 能够表示为某个整数的平方的数字称为“平方数” 虽然无法立即说出某个数是平方数&#xff0c;但经常可以断定某个数不是平方数。 因为平方数的末位只可能是&#x…...

深入探究数据结构与算法:构建强大编程基础

文章目录 1. 为什么学习数据结构与算法&#xff1f;1.1 提高编程技能1.2 解决复杂问题1.3 面试准备1.4 提高代码效率 2. 学习资源2.1 经典教材2.2 在线学习平台2.3 学习编程社区 3. 数据结构与算法的实际应用3.1 排序算法3.2 图算法3.3 字符串匹配算法 4. 结论 &#x1f389;欢…...

Android 自定义View之圆形进度条

很多场景下都用到这种进度条&#xff0c;有的还带动画效果&#xff0c; 今天我也来写一个。 写之前先拆解下它的组成&#xff1a; 底层圆形上层弧形中间文字 那我们要做的就是&#xff1a; 绘制底层圆形&#xff1b;在同位置绘制上层弧形&#xff0c;但颜色不同&#xff…...

力扣(LeetCode)算法_C++——字母异位词分组

给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”…...

【LeetCode-中等题】59. 螺旋矩阵 II

文章目录 题目方法一&#xff1a;二维数组缩圈填数字方法二&#xff1a; 题目 方法一&#xff1a;二维数组缩圈填数字 定义四个边界条件&#xff0c;每转一圈&#xff0c;把数值填进去&#xff0c;然后缩小一圈&#xff0c;直到不满足条件位置 结束循环条件可以是&#xff1a; …...

错误: 找不到或无法加载主类 Main

在用git回退到上个版本后发现&#xff0c;无法运行项目并提示 错误: 找不到或无法加载主类 Main 可以看到Main前面的图标也是号。 查了半天没有解决&#xff0c;问了个大佬&#xff0c;大佬一下就解决掉了&#xff0c;本文记录下解决过程。 错误原因是编辑器无法找到代码位置&…...

【云原生】Kubeadmin安装k8s集群

目录 前言&#xff1a; 一 环境部署 1.1 服务器部署功能 1.2 环境准备&#xff08;所有节点&#xff09; 二 安装docker&#xff08;所有节点&#xff09; 三 所有节点安装kubeadm&#xff0c;kubelet和kubectl 3.1 定义kubernetes源 3.2 开机自启kubelet 四 部署K8S集…...

Java:Springboot和React中枚举值(数据字典)的使用

目录 1、开发中的需求2、实现效果3、后端代码4、前端代码5、接口数据6、完整代码7、参考文章 1、开发中的需求 开发和使用过程中&#xff0c;通常会涉及四个角色&#xff1a;数据库管理员、后端开发人员、前端开发人员、浏览者 数据库使用int类型的数值进行存储&#xff08;e…...

git撤回 不小心 commit 进去的文件

我时候 我们可能讲一下不想提交的文件 不小心commit了进去 我们可以通过 git reset HEAD~来撤回刚才的添加记录...

qt之movetothread理解

基础概念 qt的下线程qthread&#xff0c;每个线程都有自己的事件循环exec。对象的线程上下文&#xff0c;每个对象都有自己的线程上下文&#xff0c;怎么理解呢&#xff0c;就是该对象在哪个线程创建&#xff0c;其线程上下文就是谁。每个qobject对象在创建时都有包含线程成员…...

深入剖析:垃圾回收你真的了解吗?

小熊学Java&#xff1a;https://www.javaxiaobear.cn/ 本文我们重点剖析 JVM 的垃圾回收机制。关于 JVM 垃圾回收机制面试中主要涉及这三个考题&#xff1a; JVM 中有哪些垃圾回收算法&#xff1f;它们各自有什么优劣&#xff1f; CMS 垃圾回收器是怎么工作的&#xff1f;有哪…...

ue5 物理场的应用

cable mat wpo particle 流体粒子 choas 破损 刚体 布料 cloud abp blueprint riggedbody 体积雾 毛发 全局的 局部的 非均匀的 连续变化的 也可以多个叠加 从全局 到 范围 除了vector还有scalar的值也就是0--1的黑白灰的值 但是最终输出的值的类型还是取决于这个 一…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

虚幻基础:角色旋转

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 移动组件使用控制器所需旋转&#xff1a;组件 使用 控制器旋转将旋转朝向运动&#xff1a;组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转&#xff1a;必须移动才能旋转&#xff0c;不移动不旋转控制器…...

linux设备重启后时间与网络时间不同步怎么解决?

linux设备重启后时间与网络时间不同步怎么解决&#xff1f; 设备只要一重启&#xff0c;时间又错了/偏了&#xff0c;明明刚刚对时还是对的&#xff01; 这在物联网、嵌入式开发环境特别常见&#xff0c;尤其是开发板、树莓派、rk3588 这类设备。 解决方法&#xff1a; 加硬件…...