当前位置: 首页 > 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…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

Linux中INADDR_ANY详解

在Linux网络编程中&#xff0c;INADDR_ANY 是一个特殊的IPv4地址常量&#xff08;定义在 <netinet/in.h> 头文件中&#xff09;&#xff0c;用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法&#xff0c;允许套接字监听所有本地IP地址上的连接请求。 关…...

智警杯备赛--excel模块

数据透视与图表制作 创建步骤 创建 1.在Excel的插入或者数据标签页下找到数据透视表的按钮 2.将数据放进“请选择单元格区域“中&#xff0c;点击确定 这是最终结果&#xff0c;但是由于环境启不了&#xff0c;这里用的是自己的excel&#xff0c;真实的环境中的excel根据实训…...

Spring是如何实现无代理对象的循环依赖

无代理对象的循环依赖 什么是循环依赖解决方案实现方式测试验证 引入代理对象的影响创建代理对象问题分析 源码见&#xff1a;mini-spring 什么是循环依赖 循环依赖是指在对象创建过程中&#xff0c;两个或多个对象相互依赖&#xff0c;导致创建过程陷入死循环。以下通过一个简…...