二叉树的最近公共祖先【Java实现】
题目描述
现有一棵
n个结点的二叉树(结点编号为从0到n-1,根结点为0号结点),求两个指定编号结点的最近公共祖先。
注:二叉树上两个结点A、B的最近公共祖先是指:二叉树上存在的一个结点P,使得P既是A的祖先,又是B的祖先,并且P需要离根结点尽可能远(即层号尽可能大)。
输入描述
第一行
3个整数n、k1、k2(1≤n≤50,0≤k1≤n−1,0≤k2≤n−1),分别表示二叉树的结点个数、需要求最近公共祖先的两个结点的编号;接下来
n行,每行一个结点,按顺序给出编号从0到n-1的结点的左子结点编号和右子结点编号,中间用空格隔开。如果不存在对应的子结点,那么用-1表示。
输出描述
输出一个整数,表示最近公共祖先的编号。
样例
输入
6 1 4 // 共有6个节点【编号0~5】,目标节点编号为1和4
2 5 // 0号节点的左节点为2号节点,右节点为5号节点
-1 -1 // 1号节点左右节点都为空
1 4 // 2号节点左节点为1号节点,右节点为4号节点
-1 -1 // ...依次类推
-1 -1
-1 3
输出
2 // 1号节点和4号节点在上述树结构中的祖先节点为2号节点
思路分析
-
所谓祖先节点一定是我们的目标节点或在它的上层,也就是我们得把当前节点的下面部分遍历完,才能判断当前节点是不是祖先节点。
在树的三种遍历中,先把下面遍历完在判断当前节点的遍历方式显而易见,是后序遍历,确定遍历方式是解决问题的第一步。
-
第二步是设立边界,即怎样判断当前节点是不是祖先节点,或者怎样确定它一定不是祖先节点
- 如果当前节点左子树部分存在目标节点,右子树部分也存在目标节点,那么可以确定当前节点一定是祖先节点
- 如果当前节点是目标节点,且左右子树中也存在一个目标节点,则可以确定当前节点一定是祖先节点
- 除上述两种情况外,其余情况皆为非祖先节点
-
明确步骤之后,我们设计的函数应当返回当前节点左右子树或自身是否包含目标节点,若包含返回
true,不包含返回false,并且在后序遍历过程中记录下满足条件的祖先节点。
代码实现
package homework;import java.util.Scanner;public class Main {static int ans = -1;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();TreeNode arrs[] = new TreeNode[n];int k1 = scanner.nextInt();int k2 = scanner.nextInt();for (int i = 0; i < n; i++) {TreeNode node = new TreeNode();node.left = scanner.nextInt();node.right = scanner.nextInt();arrs[i] = node;}findAncestorByPostOrder(arrs, 0, k1, k2);System.out.println(ans);}public static boolean findAncestorByPostOrder(TreeNode arrs[], int index, int k1, int k2) {if (index == -1) {return false;}boolean left = findAncestorByPostOrder(arrs, arrs[index].left, k1, k2);boolean right = findAncestorByPostOrder(arrs, arrs[index].right, k1, k2);// 说明当前节点是目标之一boolean flag = index == k1 || index == k2;// 当前节点为目标节点主要对应如下两种情况:// 1. 当左右同时为目标;// 2. 当左边或者右边有一个为目标,且当前也是目标之一if ((left && right) || ((left || right) && flag)) {ans = index;}// 如果当前节点左右存在目标节点,或者当前节点就是目标节点时返回 truereturn left || right || flag;}}class TreeNode {int left;int right;}
相关文章:
二叉树的最近公共祖先【Java实现】
题目描述 现有一棵n个结点的二叉树(结点编号为从0到n-1,根结点为0号结点),求两个指定编号结点的最近公共祖先。 注:二叉树上两个结点A、B的最近公共祖先是指:二叉树上存在的一个结点P,使得P既是…...
关闭应用程序遥测,禁止Windows收集用户信息
目录 1. 先创建还原点,防止意外 2. 界面设置 3. 服务 (1) GPEdit.msc - 本地计算机策略 - 计算机配置 - 管理模板 - Windows 组件 - 应用程序兼容性 - 关闭应用程序遥测 - 已启用 (2) GPEdit.msc - 本地计算机策略 - 计算机配置 - 管理模板 - Windows 组件 - 数…...
【备战面试】每日10道面试题打卡-Day4
本篇总结的是Java集合知识相关的面试题,后续也会更新其他相关内容 文章目录1、HashMap在JDK1.7和JDK1.8中有哪些不同?2、HashMap 的长度为什么是2的幂次方?3、HashMap的扩容操作是怎么实现的?4、HashMap是怎么解决哈希冲突的&…...
热乎的面经——初出茅庐
⭐️前言⭐️ 本篇文章记录博主与2023.03.04面试上海柯布西公司,一面所被问及的面试问题,回答答案仅供参考。 🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁 🍉博主将持续更新学习记录收获&am…...
数据库中各种锁汇总
本文汇总简记数据库中的各种锁。 名称英文名称定义解释悲观锁Pessimistic Lock在访问数据前先加锁,防止其他事务的并发修改数据通过获取锁来保证数据的独占性,从而避免并发修改数据带来的问题。乐观锁Optimistic Lock在修改数据时先不加锁,而…...
p76 - Python 开发-内外网收集 Socket子域名DNS
数据来源 Python 开发相关知识点: 1.开发基础环境配置说明 Windows10Pycharm 2.Python 开发学习的意义 学习相关安全工具原理 掌握自定义工具及拓展开发解决实战中无工具或手工麻烦批量化等情况 在二次开发 Bypass,日常任务,批量测试利用…...
QCC51XX--eFush Key加密
https://blog.csdn.net/weixin_42162924/article/details/125828901?spm=1001.2014.3001.5502 在开始讲eFush Key加密操作之前,说一下这个操作的作用就是将自己的固件采用硬件的方式进行加密。 操作步骤 1.创建一个txt文本文件,参考文档“Qualcomm BlueSuite v3.1.4 Release…...
nginx http模块
1.模块依赖2. 模块的初始化2.1 location的定义location的定义包含以下几种location [ | ~ | ~* | ^~ ] uri { ... } location name { ... }:表示精确匹配,只有请求的url路径与后面的字符串完全相等时,才会命中,不支持location嵌套~ÿ…...
守护进程 || 精灵进程
目录 守护进程(deamon) || 精灵进程 特点 什么是前台进程组 把自己写的服务器deamon deamon代码 守护进程(deamon) || 精灵进程 特点 01. 他的PPID是1(附件特征)02. COMMAND --- 称为进程启动的命令03…...
Zookeeper3.5.7版本——客户端命令行操作(znode 节点数据信息)
目录一、命令行语法二、znode 节点数据信息2.1、查看当前znode中所包含的内容2.2、查看当前节点详细数据2.3、节点详细数据解释一、命令行语法 命令行语法列表 命令基本语法功能描述help显示所有操作命令ls path使用 ls 命令来查看当前 znode 的子节点 [可监听]-w 监听子节点变…...
如何写好单测
1、为什么要写单测? 单测即单元测试(Unit Test),是对软件的基本组成单元进行的测试,比如函数、过程或者类的方法。其意义是: 功能自测,发现功能缺陷自我Code Review测试驱动开发促进代码重构并…...
CDH-6.3.2内置spark-2.4.0的BUG
1. 背景 公司最近在新建集群,全部采用开源的大数据框架,并且将之前使用的阿里云的所有服务进行下线,其中就涉及到了旧任务的迁移。 2. 任务 2.1. 简述 我接手到一个之前的 spark 任务,是读取阿里 LogStore 数据,然…...
SpringCloud之ElasticSearch笔记
ElasticSearch 初识ElasticSearch ElasticSearch是什么 ElasticSearch一个基于Lucene的底层的开源的分布式搜索引擎,可用来实现搜索,日志统计,分析,系统监控 正向索引和倒排索引 正向索引:逐条扫描(my…...
数字图像学笔记 —— 17. 图像退化与复原(自适应滤波之「最小二乘方滤波」)
文章目录维纳滤波的缺点约束最小二乘方滤波给一个实际例子吧维纳滤波的缺点 维纳滤波(Wiener Filter),虽然是一种非常强大的退化图像还原算法,但是从实验过程我们也发现它存在着致命的缺陷,那就是要求输入退化系统的 …...
2023-03-05:ffmpeg推送本地视频至lal流媒体服务器(以RTMP为例),请用go语言编写。
2023-03-05:ffmpeg推送本地视频至lal流媒体服务器(以RTMP为例),请用go语言编写。 答案2023-03-05: 使用 github.com/moonfdd/ffmpeg-go 库。 先启动lal流媒体服务器软件,然后再执行命令: go…...
MathType7最新版免费数学公式编辑器
话说我也算是 MathType准资深(DB)用户了,当然自从感觉用DB不好之后,我基本上已经抛弃它了,只是前不久因为个别原因又捡起来用了用,30天试用期间又比较深入的折腾了下,也算是变成半个MathType砖家,coco玛奇朵简单介绍一下这款软件:在很可能看到这儿的你还没有出生的某个年月&…...
一文带你入门angular(中)
一、angular中的dom操作原生和ViewChild两种方式以及css3动画 1.原生操作 import { Component } from angular/core;Component({selector: app-footer,templateUrl: ./footer.component.html,styleUrls: [./footer.component.scss] }) export class FooterComponent {flag: b…...
单例设计模式共享数据问题分析、解决(c++11)设计多线程。
系列文章目录 单例设计模式共享数据问题分析、解决; 文章目录系列文章目录前言一、单例模式1.1 基本概念1.2 单例设计模式共享数据问题分析、解决1.3 std::call_once()介绍二、代码案例1.代码示例总结前言 关键内容:c11、多线程、共享数据、单例类 本章内容参考git…...
Embedding-based Retrieval in Facebook Search
facebook的社交网络检索与传统的搜索检索的差异是,除了考虑文本,还要考虑搜索者的背景。通用搜索主要考虑的是文本匹配,并没有涉及到个性化。像淘宝,youtube这些其实都是涉及到了用户自身行为的,除了搜索还有推荐&…...
xmu 离散数学 卢杨班作业详解【8-12章】
文章目录第八章 树23456810第九章46811第十章24567第十一章14571116第十二章131317第八章 树 2 (2) 设有k片树叶 2∗m2∗43∗3k2*m2*43*3k2∗m2∗43∗3k n23kn23kn23k mn−1mn-1mn−1 联立解得k9 T中有9片树叶 3 有三颗非同构的生成树 4 (1) c --abc e–abed f–dgf…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
