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. 计算右侧小于当前元素的个数

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/116033.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

良品铺子聚焦高品质,打造零食王国

出品| 大力财经 文 | 魏力 8月29日&#xff0c;休闲食品企业良品铺子发布2023年半年报显示&#xff0c;实现营业收入39.87亿元&#xff0c;归母净利润1.89亿元。 值得注意的是&#xff0c;在全球经济增速不强的背景下&#xff0c;良品铺子上半年&#xff0c;新开店323家&#…

Ubuntu 18.04上无法播放MP4格式视频解决办法

ubuntu18.04系统无法播放MP4格式视频&#xff0c;提示如下图所示&#xff1a; 解决办法&#xff1a; 1、首先&#xff0c;确保ubuntu系统已完全更新。可使用以下命令更新软件包列表&#xff1a;sudo apt update&#xff0c;然后使用以下命令升级所有已安装的软件包&#xff1a…

【SQL应知应会】索引 • Oracle版:B-树索引;位图索引;函数索引;单列与复合索引;分区索引

欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享&#xff0c;与更多的人进行学习交流 本文免费学习&#xff0c;自发文起3天后&#xff0c;会收录于SQL应知应会专栏,本专栏主要用于记录对于数据库的一些学习&#xff0c;有基础也有进阶&#xff0c;有MySQL也有Oracle …

深入剖析 Golang 程序启动原理 - 从 ELF 入口点到GMP初始化到执行 main!

大家好&#xff0c;我是飞哥&#xff01; 在过去的开发工作中&#xff0c;大家都是通过创建进程或者线程来工作的。Linux进程是如何创建出来的&#xff1f; 、聊聊Linux中线程和进程的联系与区别&#xff01; 和你的新进程是如何被内核调度执行到的&#xff1f; 这几篇文章就是…

K 次取反后最大化的数组和【贪心算法】

1005 . K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k &#xff0c;按以下方法修改该数组&#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后&#xff0c;返回数组 可能…

打击儿童性虐待,遭多家机构反对,苹果宣布停止开发CSAM检测计划

据报道&#xff0c;苹果公司曾计划在其iCloud云服务中引入一项儿童性虐待资料&#xff08;CSAM&#xff09;检测计划&#xff0c;但由于反对声浪日益高涨&#xff0c;该计划最终宣布停止开发。CSAM检测计划的原本目的是为了帮助阻止儿童性虐待资料的传播&#xff0c;保护儿童的…

Go操作各大消息队列教程(RabbitMQ、Kafka)

Go操作各大消息队列教程 1 RabbitMQ 1.1 概念 ①基本名词 当前市面上mq的产品很多&#xff0c;比如RabbitMQ、Kafka、ActiveMQ、ZeroMQ和阿里巴巴捐献给Apache的RocketMQ。甚至连redis这种NoSQL都支持MQ的功能。 Broker&#xff1a;表示消息队列服务实体Virtual Host&#x…

关于购买AirPods,现在是否为最佳时机?

我们不需要解释你为什么想要AirPods。苹果对真正的无线耳机的采用彻底改变了市场&#xff0c;并从那时起大量销售。你总是在记者、同事和名人的耳朵里看到它们——尤其是在我们这个远程工作和Zoom会议的时代。 真正的问题是&#xff0c;你应该现在就买一个&#xff0c;还是在几…

MySQL索引,事务和存储引擎

一、索引 1、索引的概念 ●索引是一个排序的列表&#xff0c;在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址&#xff08;类似于C语言的链表通过指针指向数据记录的内存地址&#xff09;。 ●使用索引后可以不用扫描全表来定位某行的数据&#xff0c;而是先…

博流RISC-V芯片Eclipse环境搭建

文章目录 1、下载 Eclipse2、导入 bouffalo_sdk3、编译4、烧录5、使用ninja编译 之前编译是通过 VSCode 编译&#xff0c;通过手工输入 make 命令编译&#xff0c;我们也可以通过 Eclipse 可视化 IDE 来编译、烧录。 1、下载 Eclipse 至 Eclipse 官网 https://www.eclipse.org…

IntelliJ IDEA 2023.2.1 Android开发变化

IntelliJ IDEA 2023.2.1之前的版本&#xff0c;Empty Activity是指Empty View Activity&#xff0c;而现在Empty Activity是指Empty Compose Activity&#xff0c;另外多了一个Empty View Activity的选项 这表明官方推荐使用Compose这种声明式的编程方式来描述UI&#xff0c;命…

springboot上线打包+vuecli2部署在linux服务器上(打包上线)

这里也是记录一下springboot的上线打包流程,我这里前端使用的是vuecli2 springboot的依赖是2.7.9的版本 前端是使用的vue2 打包前,你的linux上必须要先安装,tomcat\java\nginx springboot打包 springboot打包点击一下,等maven编译打包成功在target文件下找到,jar包, 然后,把j…

C语言:指针的运算

一、指针 或 - 整数 指针 或 - 整数表示指针跳过几个字节&#xff08;具体跳过几个字节由指针类型决定&#xff09; 本文不做具体讲解&#xff0c;详解跳转链接&#xff1a; 《C语言&#xff1a;指针类型的意义》 二、指针 - 指针 前提条件&#xff1a;指针类型相同并且指向同…

[学习笔记]斜率优化dp 总结

前言&#xff1a; 我们学过不少优化类的算法了&#xff0c;大部分都是基于凸函数的性质给出的优化&#xff0c;比如Slope Trick&#xff0c;Wqs二分&#xff0c;又比如今天的斜率优化&#xff08;不知道什么时候会有空把Slope Trick写掉&#xff09; 正文&#xff1a; 我们考…

应用案例 | 基于三维机器视觉的机器人麻袋拆垛应用解决方案

​Part.1 项目背景 在现代物流和制造行业中&#xff0c;麻袋的拆垛操作是一个重要且频繁的任务。传统的麻袋拆垛工作通常由人工完成&#xff0c;分拣效率较低&#xff0c;人力成本较高&#xff0c;现场麻袋堆叠、变形严重&#xff0c;垛型不规则、不固定&#xff0c;严重影响分…

拓世科技集团 | “书剑人生”李步云学术思想研讨会暨李步云先生九十华诞志庆

2023年&#xff0c;中国改革开放迎来了45周年&#xff0c;改革春风浩荡&#xff0c;席卷神州大地&#xff0c;45年间&#xff0c;中国特色社会主义伟大事业大步迈入崭新境界&#xff0c;一路上结出了饶为丰硕的果实。中华民族在这45年间的砥砺前行&#xff0c;不仅使中国的经济…

解决uniapp下拉框 内容被覆盖的问题

1. 下拉框 内容被覆盖的问题 场景: 现在是下拉框被表格覆盖了 解决办法: 在表格上添加css 样式来解决这个问题 .add-table{display: static;overflow: visible; } display: static: 将元素会按照默认的布局方式进行显示&#xff0c;不会分为块状或行内元素。 overflow: vi…

【用unity实现100个游戏之7】从零开始制作一个仿杀戮尖塔卡牌回合制游戏

文章目录 前言素材资源开始一、UI框架二、挂载脚本三、事件监听&#xff0c;用于绑定按钮事件四、声音管理器五、excel转txt文本六、游戏配置七、用户信息表八、战斗管理器九、 敌人管理器十、玩家血量、能量、防御值、卡牌数十一、敌人血量 行动显示逻辑十二、UI提示效果实现十…

PHP旅游管理系统Dreamweaver开发mysql数据库web结构php编程计算机网页

一、源码特点 PHP 旅游管理系统是一套完善的web设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 PHP 旅游管理系统 源码下载地址&#xff1a; https://download.csdn.net/download/qq_41…

Docker切换文件系统为VFS

一、介绍 Docker支持AUFS、Btrfs、Device Mapper、OverlayFS、VFS、ZFS六种不同的存储驱动。 1. AUFS AUFS是一种常见的存储驱动程序&#xff0c;它也使用了Linux内核的AUFS文件系统。它的优点是支持所有的Linux发行版&#xff0c;可以在不同的容器之间共享文件系统&#xf…