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 题目-中等难度 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p…...
Git常见问题:git pull 和 git pull --rebase二者区别
git pull 和 git pull --rebase 都是从远程仓库获取最新的更改并将其合并到本地分支。但它们之间的区别在于合并方式。以下是它们之间的主要区别: git pull: 当你执行 git pull 时,Git 会执行以下两个操作: git fetchÿ…...
关于HarmonyOS元服务的主题演讲与合作签约
一、感言 坚持中,总会有很多意想不到的收获。 前几次参与HDC时更多的是观众、开发者、专家的身份,以参观、学习、交流为主。 通过几年的努力,和HarmonyOS功能成长,在2023年的HDC大会中,有了我的演讲,并带领…...
cache 学习
好文章: Cache的基本原理 - 知乎...
SSM - Springboot - MyBatis-Plus 全栈体系(六)
第二章 SpringFramework 四、SpringIoC 实践和应用 3. 基于 注解 方式管理 Bean 3.1 实验一:Bean 注解标记和扫描 (IoC) 3.1.1 注解理解 和 XML 配置文件一样,注解本身并不能执行,注解本身仅仅只是做一个标记,具体的功能是框…...
【Flutter】引入网络图片时,提示:Failed host lookup: ‘[图片host]‘
在使用 NetworkImage 组件加载外部图片时,提示 Failed host lookup: [图片host] 错误。 排查方向 1、清理缓存 解决方案: 尝试flutter clean清空缓存后重新安装依赖flutter pub get重新构建项目flutter create . 走完上述三个步骤后,再次…...
Python基础教程:索引和切片
前言 嗨喽,大家好呀~这里是爱看美女的茜茜呐 索引(下标) 索引又称下标,用来表示可迭代对象中的某个元素的位置。 用正整数表示的索引值,从左向右定位,从 0 开始计数,如 0,1&#…...
JVM基础面试题
JDK、JRE、JVM的关系 JVM Java虚拟机,它只识别.class类型文件,它能将class文件中的字节码指令进行识别并调用操作系统向上的API完成动作。 JRE Java运行时环境。它主要包含两部分:Jvm的标准实现和Java的一些基本类库。相对于JVM来说,JRE多出来…...
蓝桥杯官网填空题(平方末尾)
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 能够表示为某个整数的平方的数字称为“平方数” 虽然无法立即说出某个数是平方数,但经常可以断定某个数不是平方数。 因为平方数的末位只可能是&#x…...
深入探究数据结构与算法:构建强大编程基础
文章目录 1. 为什么学习数据结构与算法?1.1 提高编程技能1.2 解决复杂问题1.3 面试准备1.4 提高代码效率 2. 学习资源2.1 经典教材2.2 在线学习平台2.3 学习编程社区 3. 数据结构与算法的实际应用3.1 排序算法3.2 图算法3.3 字符串匹配算法 4. 结论 🎉欢…...
Android 自定义View之圆形进度条
很多场景下都用到这种进度条,有的还带动画效果, 今天我也来写一个。 写之前先拆解下它的组成: 底层圆形上层弧形中间文字 那我们要做的就是: 绘制底层圆形;在同位置绘制上层弧形,但颜色不同ÿ…...
力扣(LeetCode)算法_C++——字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”…...
【LeetCode-中等题】59. 螺旋矩阵 II
文章目录 题目方法一:二维数组缩圈填数字方法二: 题目 方法一:二维数组缩圈填数字 定义四个边界条件,每转一圈,把数值填进去,然后缩小一圈,直到不满足条件位置 结束循环条件可以是: …...
错误: 找不到或无法加载主类 Main
在用git回退到上个版本后发现,无法运行项目并提示 错误: 找不到或无法加载主类 Main 可以看到Main前面的图标也是号。 查了半天没有解决,问了个大佬,大佬一下就解决掉了,本文记录下解决过程。 错误原因是编辑器无法找到代码位置&…...
【云原生】Kubeadmin安装k8s集群
目录 前言: 一 环境部署 1.1 服务器部署功能 1.2 环境准备(所有节点) 二 安装docker(所有节点) 三 所有节点安装kubeadm,kubelet和kubectl 3.1 定义kubernetes源 3.2 开机自启kubelet 四 部署K8S集…...
Java:Springboot和React中枚举值(数据字典)的使用
目录 1、开发中的需求2、实现效果3、后端代码4、前端代码5、接口数据6、完整代码7、参考文章 1、开发中的需求 开发和使用过程中,通常会涉及四个角色:数据库管理员、后端开发人员、前端开发人员、浏览者 数据库使用int类型的数值进行存储(e…...
git撤回 不小心 commit 进去的文件
我时候 我们可能讲一下不想提交的文件 不小心commit了进去 我们可以通过 git reset HEAD~来撤回刚才的添加记录...
qt之movetothread理解
基础概念 qt的下线程qthread,每个线程都有自己的事件循环exec。对象的线程上下文,每个对象都有自己的线程上下文,怎么理解呢,就是该对象在哪个线程创建,其线程上下文就是谁。每个qobject对象在创建时都有包含线程成员…...
深入剖析:垃圾回收你真的了解吗?
小熊学Java:https://www.javaxiaobear.cn/ 本文我们重点剖析 JVM 的垃圾回收机制。关于 JVM 垃圾回收机制面试中主要涉及这三个考题: JVM 中有哪些垃圾回收算法?它们各自有什么优劣? CMS 垃圾回收器是怎么工作的?有哪…...
ue5 物理场的应用
cable mat wpo particle 流体粒子 choas 破损 刚体 布料 cloud abp blueprint riggedbody 体积雾 毛发 全局的 局部的 非均匀的 连续变化的 也可以多个叠加 从全局 到 范围 除了vector还有scalar的值也就是0--1的黑白灰的值 但是最终输出的值的类型还是取决于这个 一…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
