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

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)

二叉树的最近公共祖先 题目描述递归法代码演示 上期经典 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q …...

spacy安装旧版本en_core_web_sm的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

Qt +VTK+Cmake 编译和环境配置(第一篇 采坑)

VTK下载地址&#xff1a;https://vtk.org/download/ cmake下载地址&#xff1a;https://cmake.org/download/ 版本对应方面&#xff0c;如果你的项目对版本没有要求&#xff0c;就不用在意。我就是自己随机搭建的&#xff0c;VTK选择最新版本吧&#xff0c;如果后面其他的库不…...

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南宁师范大学图书馆

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书南宁师范大学图书馆...

C++/C# : C#和C++的不同

C#和C是两种不同的编程语言&#xff0c;虽然在某些方面它们具有相似之处&#xff0c;但它们也有一些明显的不同点&#xff0c;如下&#xff1a; C是一种静态类型编程语言&#xff0c;而C#是一种动态类型编程语言。 C允许开发者手动管理内存的分配和释放&#xff0c;但是C#的垃…...

PCL-直通滤波器原理及实验

文章目录 原理使用过程代码实验总结 原理 直通滤波器的作用是过滤在指定维度方向上取值不在给定值域内的点&#xff0c;即点云数据有xyz三维坐标&#xff0c;选择一个方向的维度的数据&#xff0c;设置一个范围&#xff0c;在这个范围中的点云会被保留&#xff0c;不在此范围内…...

数学建模:相关性分析

&#x1f506; 文章首发于我的个人博客&#xff1a;欢迎大佬们来逛逛 数学建模&#xff1a;相关性分析 文章目录 数学建模&#xff1a;相关性分析相关性分析两变量的相关分析PearsonSpearmanKendall tua-b 双变量关系强度测量的指标相关系数的性质代码实现example偏相关分析 相…...

thinkPHP项目搭建

1 宝塔添加站点 &#xff08;1&#xff09;打开命令提示行&#xff0c;输入以下命令&#xff0c;找到hosts文件。 for /f %P in (dir %windir%\WinSxS\hosts /b /s) do copy %P %windir%\System32\drivers\etc & echo %P & Notepad %P &#xff08;2&#xff09;添加域…...

C++中几种处理函数返回值的方式

目录 C中几种处理函数返回值的方式&#xff1a;值返回引用返回指针返回总结 C中几种处理函数返回值的方式&#xff1a; 值返回 函数可以返回一个具体的值&#xff0c;例如整数、浮点数、结构体、类对象等。返回值被复制到函数调用点&#xff0c;在调用点可以直接使用或赋给其…...

跟我学c++中级篇——c++中的Abominable Function Types

一、Abominable Function Types Abominable Function Types,令人讨厌&#xff08;憎恶&#xff09;的函数类型。这个在c的技术点中&#xff0c;很少有人了解。那么什么是Abominable Function Types呢&#xff1f;看下面的例子&#xff1a; using func void(); using func…...

计算机毕设之基于python+django+mysql的影片数据爬取与数据分析(包含源码+文档+部署教程)

影片数据爬取与数据分析分为两个部分&#xff0c;即管理员和用户。该系统是根据用户的实际需求开发的&#xff0c;贴近生活。从管理员处获得的指定账号和密码可用于进入系统和使用相关的系统应用程序。管理员拥有最大的权限&#xff0c;其次是用户。管理员一般负责整个系统的运…...

slog正式版来了:Go日志记录新选择!

在大约一年前&#xff0c;我就写下了《slog&#xff1a;Go官方版结构化日志包[1]》一文&#xff0c;文中介绍了Go团队正在设计并计划在下一个Go版本中落地的Go官方结构化日志包&#xff1a;slog[2]。但slog并未如预期在Go 1.20版本[3]中落地&#xff0c;而是在golang.org/x/exp…...

华为静态路由配置实验(超详细讲解+详细命令行)

系列文章目录 华为数通学习&#xff08;7&#xff09; 前言 一&#xff0c;静态路由配置 二&#xff0c;网络地址配置 AR1的配置&#xff1a; AR2的配置&#xff1a; AR3的配置&#xff1a; 三&#xff0c;测试是否连通 AR1的配置: 讲解&#xff1a; AR2的配置&#…...

axios源码学习

1 判断一个对象是否普通对象 Symbol.toStringTag&#xff1a;可以修改Object.prototype.toString.call返回的后缀&#xff0c;普通对象自带该属性&#xff0c;不需要设置&#xff0c;如果设置说明该对象不是普通对象Symbol.iterator&#xff1a;拥有该属性的对象可以使用for o…...

【SpingBoot】详细介绍SpringBoot项目中前端请求到数据库再返回前端的完整数据流转,并用代码实现

在SpringBoot项目中&#xff0c;前端请求到最终返回的完整数据流转一般包括以下几个步骤&#xff1a; 前端发送HTTP请求到后端Controller。 Controller接收到请求后&#xff0c;调用相关Service处理业务逻辑。 Service调用DAO层获取数据。 DAO层访问数据库获取数据。 数据库…...

kubesphere devops使用

一、创建项目 1 创建项目 企业管理员切换到相应企业空间(租户),创建项目&#xff0c;k8s集群会创建一个相同名字的namespace。如下图所示管理员创建一个ipaas-devops项目。 2.创建镜像拉取密钥信息 进入项目如ipaas-devops&#xff0c;选择配置->保密字典->创建&#xf…...

Selenium如何用于编写自动化测试脚本?

Selenium如何用于编写自动化测试脚本&#xff1f;它提供了许多测试工具和API&#xff0c;可以与浏览器交互&#xff0c;模拟用户操作&#xff0c;检查网页的各个方面。下面是一些步骤&#xff0c;可以帮助你编写Selenium自动化测试脚本。 1、安装Selenium库和浏览器驱动程序 首…...

linux入门到精通-第二章-常用命令和工具

目录 概述命令格式帮助文档内建命令外部命令&#xff08;--help&#xff09;帮助文档查看man查看谁登陆过电脑 文件目录命令创建目录显示目录结构删除目录 文件相关命令ls命令touchcprm删除mv移动命令 文件查看命令cat 文件内容查看命令less 查看文件内容head 从文件头部查看ta…...

C语言初阶测评题:测试你的基础知识和编程技能!!

&#x1f493;博客主页&#xff1a;江池俊的博客⏩收录专栏&#xff1a;C语言刷题专栏&#x1f449;专栏推荐&#xff1a;✅C语言初阶之路 ✅C语言进阶之路&#x1f4bb;代码仓库&#xff1a;江池俊的代码仓库&#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐ 文…...

使用HTTPS模式建立高效爬虫IP服务器详细步骤

嘿&#xff0c;各位爬虫小伙伴们&#xff01;想要自己建立一个高效的爬虫IP服务器吗&#xff1f;今天我就来分享一个简单而强大的解决方案——使用HTTPS模式建立工具&#xff01;本文将为你提供详细的操作步骤和代码示例&#xff0c;让你快速上手&#xff0c;轻松建立自己的爬虫…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...