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

二叉树的最近公共祖先【Java实现】

题目描述

现有一棵n个结点的二叉树(结点编号为从0n-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行,每行一个结点,按顺序给出编号从0n-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
image-20230305170515544

输出

2	// 1号节点和4号节点在上述树结构中的祖先节点为2号节点

思路分析

  • 所谓祖先节点一定是我们的目标节点或在它的上层,也就是我们得把当前节点的下面部分遍历完,才能判断当前节点是不是祖先节点。

    在树的三种遍历中,先把下面遍历完在判断当前节点的遍历方式显而易见,是后序遍历,确定遍历方式是解决问题的第一步。

  • 第二步是设立边界,即怎样判断当前节点是不是祖先节点,或者怎样确定它一定不是祖先节点

    1. 如果当前节点左子树部分存在目标节点,右子树部分也存在目标节点,那么可以确定当前节点一定是祖先节点
    2. 如果当前节点是目标节点,且左右子树中也存在一个目标节点,则可以确定当前节点一定是祖先节点
    3. 除上述两种情况外,其余情况皆为非祖先节点
  • 明确步骤之后,我们设计的函数应当返回当前节点左右子树或自身是否包含目标节点,若包含返回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个结点的二叉树&#xff08;结点编号为从0到n-1&#xff0c;根结点为0号结点&#xff09;&#xff0c;求两个指定编号结点的最近公共祖先。 注&#xff1a;二叉树上两个结点A、B的最近公共祖先是指&#xff1a;二叉树上存在的一个结点P&#xff0c;使得P既是…...

关闭应用程序遥测,禁止Windows收集用户信息

目录 1. 先创建还原点&#xff0c;防止意外 2. 界面设置 3. 服务 (1) GPEdit.msc - 本地计算机策略 - 计算机配置 - 管理模板 - Windows 组件 - 应用程序兼容性 - 关闭应用程序遥测 - 已启用 (2) GPEdit.msc - 本地计算机策略 - 计算机配置 - 管理模板 - Windows 组件 - 数…...

【备战面试】每日10道面试题打卡-Day4

本篇总结的是Java集合知识相关的面试题&#xff0c;后续也会更新其他相关内容 文章目录1、HashMap在JDK1.7和JDK1.8中有哪些不同&#xff1f;2、HashMap 的长度为什么是2的幂次方&#xff1f;3、HashMap的扩容操作是怎么实现的&#xff1f;4、HashMap是怎么解决哈希冲突的&…...

热乎的面经——初出茅庐

⭐️前言⭐️ 本篇文章记录博主与2023.03.04面试上海柯布西公司&#xff0c;一面所被问及的面试问题&#xff0c;回答答案仅供参考。 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主将持续更新学习记录收获&am…...

数据库中各种锁汇总

本文汇总简记数据库中的各种锁。 名称英文名称定义解释悲观锁Pessimistic Lock在访问数据前先加锁&#xff0c;防止其他事务的并发修改数据通过获取锁来保证数据的独占性&#xff0c;从而避免并发修改数据带来的问题。乐观锁Optimistic Lock在修改数据时先不加锁&#xff0c;而…...

p76 - Python 开发-内外网收集 Socket子域名DNS

数据来源 Python 开发相关知识点&#xff1a; 1.开发基础环境配置说明 Windows10Pycharm 2.Python 开发学习的意义 学习相关安全工具原理 掌握自定义工具及拓展开发解决实战中无工具或手工麻烦批量化等情况 在二次开发 Bypass&#xff0c;日常任务&#xff0c;批量测试利用…...

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 { ... }:表示精确匹配&#xff0c;只有请求的url路径与后面的字符串完全相等时&#xff0c;才会命中&#xff0c;不支持location嵌套~&#xff…...

守护进程 || 精灵进程

目录 守护进程&#xff08;deamon&#xff09; || 精灵进程 特点 什么是前台进程组 把自己写的服务器deamon deamon代码 守护进程&#xff08;deamon&#xff09; || 精灵进程 特点 01. 他的PPID是1&#xff08;附件特征&#xff09;02. COMMAND --- 称为进程启动的命令03…...

Zookeeper3.5.7版本——客户端命令行操作(znode 节点数据信息)

目录一、命令行语法二、znode 节点数据信息2.1、查看当前znode中所包含的内容2.2、查看当前节点详细数据2.3、节点详细数据解释一、命令行语法 命令行语法列表 命令基本语法功能描述help显示所有操作命令ls path使用 ls 命令来查看当前 znode 的子节点 [可监听]-w 监听子节点变…...

如何写好单测

1、为什么要写单测&#xff1f; 单测即单元测试&#xff08;Unit Test&#xff09;&#xff0c;是对软件的基本组成单元进行的测试&#xff0c;比如函数、过程或者类的方法。其意义是&#xff1a; 功能自测&#xff0c;发现功能缺陷自我Code Review测试驱动开发促进代码重构并…...

CDH-6.3.2内置spark-2.4.0的BUG

1. 背景 公司最近在新建集群&#xff0c;全部采用开源的大数据框架&#xff0c;并且将之前使用的阿里云的所有服务进行下线&#xff0c;其中就涉及到了旧任务的迁移。 2. 任务 2.1. 简述 我接手到一个之前的 spark 任务&#xff0c;是读取阿里 LogStore 数据&#xff0c;然…...

SpringCloud之ElasticSearch笔记

ElasticSearch 初识ElasticSearch ElasticSearch是什么 ElasticSearch一个基于Lucene的底层的开源的分布式搜索引擎&#xff0c;可用来实现搜索&#xff0c;日志统计&#xff0c;分析&#xff0c;系统监控 正向索引和倒排索引 正向索引&#xff1a;逐条扫描&#xff08;my…...

数字图像学笔记 —— 17. 图像退化与复原(自适应滤波之「最小二乘方滤波」)

文章目录维纳滤波的缺点约束最小二乘方滤波给一个实际例子吧维纳滤波的缺点 维纳滤波&#xff08;Wiener Filter&#xff09;&#xff0c;虽然是一种非常强大的退化图像还原算法&#xff0c;但是从实验过程我们也发现它存在着致命的缺陷&#xff0c;那就是要求输入退化系统的 …...

2023-03-05:ffmpeg推送本地视频至lal流媒体服务器(以RTMP为例),请用go语言编写。

2023-03-05&#xff1a;ffmpeg推送本地视频至lal流媒体服务器&#xff08;以RTMP为例&#xff09;&#xff0c;请用go语言编写。 答案2023-03-05&#xff1a; 使用 github.com/moonfdd/ffmpeg-go 库。 先启动lal流媒体服务器软件&#xff0c;然后再执行命令&#xff1a; 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.代码示例总结前言 关键内容&#xff1a;c11、多线程、共享数据、单例类 本章内容参考git…...

Embedding-based Retrieval in Facebook Search

facebook的社交网络检索与传统的搜索检索的差异是&#xff0c;除了考虑文本&#xff0c;还要考虑搜索者的背景。通用搜索主要考虑的是文本匹配&#xff0c;并没有涉及到个性化。像淘宝&#xff0c;youtube这些其实都是涉及到了用户自身行为的&#xff0c;除了搜索还有推荐&…...

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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...