二叉树的最近公共祖先【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…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
VSCode 使用CMake 构建 Qt 5 窗口程序
首先,目录结构如下图: 运行效果: cmake -B build cmake --build build 运行: windeployqt.exe F:\testQt5\build\Debug\app.exe main.cpp #include "mainwindow.h"#include <QAppli...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
