leetcode236. 二叉树的最近公共祖先(java)
二叉树的最近公共祖先
- 题目描述
- 递归法
- 代码演示
- 上期经典
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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, 1e5] 内。
-109 <= Node.val <= 1e9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
递归法
这道题目中说, p 和 q 均存在于给定的二叉树中。 但会有不同的情况:
两个节点的最近公共祖先其实就是这两个节点向根节点的「延长线」的交汇点,那么对于任意一个节点,它怎么才能知道自己是不是p和q的最近公共祖先?
如果一个节点能够在它的左右子树中分别找到p和q,则该节点为LCA节点。
代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return find(root, p.val, q.val);
}// 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
TreeNode find(TreeNode root, int val1, int val2) {if(root == null){return null;}//在root节点=p 或者 ==q ,那么这个节点肯定就是最近祖先if(root.val == val1 || root.val == val2){return root;}TreeNode left = find(root.left,val1,val2);TreeNode right = find(root.right,val1,val2);//在root节点的左右节点找到p和q 那么root 就是最近公共祖先if(left != null && right != null){return root;}//如果root 上没找到,那么肯定是左右子节点上其中一个。return left != null ? left : right;
}
}
不过需要注意的是,这两道题的题目都明确告诉我们这些节点必定存在于二叉树中,如果没有这个前提条件,就需要修改代码了。
上期经典
LC315. 计算右侧小于当前元素的个数
相关文章:
leetcode236. 二叉树的最近公共祖先(java)
二叉树的最近公共祖先 题目描述递归法代码演示 上期经典 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q …...
spacy安装旧版本en_core_web_sm的解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...
Qt +VTK+Cmake 编译和环境配置(第一篇 采坑)
VTK下载地址:https://vtk.org/download/ cmake下载地址:https://cmake.org/download/ 版本对应方面,如果你的项目对版本没有要求,就不用在意。我就是自己随机搭建的,VTK选择最新版本吧,如果后面其他的库不…...
2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南宁师范大学图书馆
2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南宁师范大学图书馆...
C++/C# : C#和C++的不同
C#和C是两种不同的编程语言,虽然在某些方面它们具有相似之处,但它们也有一些明显的不同点,如下: C是一种静态类型编程语言,而C#是一种动态类型编程语言。 C允许开发者手动管理内存的分配和释放,但是C#的垃…...
PCL-直通滤波器原理及实验
文章目录 原理使用过程代码实验总结 原理 直通滤波器的作用是过滤在指定维度方向上取值不在给定值域内的点,即点云数据有xyz三维坐标,选择一个方向的维度的数据,设置一个范围,在这个范围中的点云会被保留,不在此范围内…...
数学建模:相关性分析
🔆 文章首发于我的个人博客:欢迎大佬们来逛逛 数学建模:相关性分析 文章目录 数学建模:相关性分析相关性分析两变量的相关分析PearsonSpearmanKendall tua-b 双变量关系强度测量的指标相关系数的性质代码实现example偏相关分析 相…...
thinkPHP项目搭建
1 宝塔添加站点 (1)打开命令提示行,输入以下命令,找到hosts文件。 for /f %P in (dir %windir%\WinSxS\hosts /b /s) do copy %P %windir%\System32\drivers\etc & echo %P & Notepad %P (2)添加域…...
C++中几种处理函数返回值的方式
目录 C中几种处理函数返回值的方式:值返回引用返回指针返回总结 C中几种处理函数返回值的方式: 值返回 函数可以返回一个具体的值,例如整数、浮点数、结构体、类对象等。返回值被复制到函数调用点,在调用点可以直接使用或赋给其…...
跟我学c++中级篇——c++中的Abominable Function Types
一、Abominable Function Types Abominable Function Types,令人讨厌(憎恶)的函数类型。这个在c的技术点中,很少有人了解。那么什么是Abominable Function Types呢?看下面的例子: using func void(); using func…...
计算机毕设之基于python+django+mysql的影片数据爬取与数据分析(包含源码+文档+部署教程)
影片数据爬取与数据分析分为两个部分,即管理员和用户。该系统是根据用户的实际需求开发的,贴近生活。从管理员处获得的指定账号和密码可用于进入系统和使用相关的系统应用程序。管理员拥有最大的权限,其次是用户。管理员一般负责整个系统的运…...
slog正式版来了:Go日志记录新选择!
在大约一年前,我就写下了《slog:Go官方版结构化日志包[1]》一文,文中介绍了Go团队正在设计并计划在下一个Go版本中落地的Go官方结构化日志包:slog[2]。但slog并未如预期在Go 1.20版本[3]中落地,而是在golang.org/x/exp…...
华为静态路由配置实验(超详细讲解+详细命令行)
系列文章目录 华为数通学习(7) 前言 一,静态路由配置 二,网络地址配置 AR1的配置: AR2的配置: AR3的配置: 三,测试是否连通 AR1的配置: 讲解: AR2的配置&#…...
axios源码学习
1 判断一个对象是否普通对象 Symbol.toStringTag:可以修改Object.prototype.toString.call返回的后缀,普通对象自带该属性,不需要设置,如果设置说明该对象不是普通对象Symbol.iterator:拥有该属性的对象可以使用for o…...
【SpingBoot】详细介绍SpringBoot项目中前端请求到数据库再返回前端的完整数据流转,并用代码实现
在SpringBoot项目中,前端请求到最终返回的完整数据流转一般包括以下几个步骤: 前端发送HTTP请求到后端Controller。 Controller接收到请求后,调用相关Service处理业务逻辑。 Service调用DAO层获取数据。 DAO层访问数据库获取数据。 数据库…...
kubesphere devops使用
一、创建项目 1 创建项目 企业管理员切换到相应企业空间(租户),创建项目,k8s集群会创建一个相同名字的namespace。如下图所示管理员创建一个ipaas-devops项目。 2.创建镜像拉取密钥信息 进入项目如ipaas-devops,选择配置->保密字典->创建…...
Selenium如何用于编写自动化测试脚本?
Selenium如何用于编写自动化测试脚本?它提供了许多测试工具和API,可以与浏览器交互,模拟用户操作,检查网页的各个方面。下面是一些步骤,可以帮助你编写Selenium自动化测试脚本。 1、安装Selenium库和浏览器驱动程序 首…...
linux入门到精通-第二章-常用命令和工具
目录 概述命令格式帮助文档内建命令外部命令(--help)帮助文档查看man查看谁登陆过电脑 文件目录命令创建目录显示目录结构删除目录 文件相关命令ls命令touchcprm删除mv移动命令 文件查看命令cat 文件内容查看命令less 查看文件内容head 从文件头部查看ta…...
C语言初阶测评题:测试你的基础知识和编程技能!!
💓博客主页:江池俊的博客⏩收录专栏:C语言刷题专栏👉专栏推荐:✅C语言初阶之路 ✅C语言进阶之路💻代码仓库:江池俊的代码仓库🎉欢迎大家点赞👍评论📝收藏⭐ 文…...
使用HTTPS模式建立高效爬虫IP服务器详细步骤
嘿,各位爬虫小伙伴们!想要自己建立一个高效的爬虫IP服务器吗?今天我就来分享一个简单而强大的解决方案——使用HTTPS模式建立工具!本文将为你提供详细的操作步骤和代码示例,让你快速上手,轻松建立自己的爬虫…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...



输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4