寻找二叉树的最低公共祖先节点

两个节点沿二叉树向上找,找到的第一个公共的节点

例:D和F之间的最低公共节点:B
D → B; F → E → B;
E和G最低公共节点:A
E → B → A; G → C → A;
B和F最低公共节点:B
B ; F → E → B;
方法一:
从两个节点开始,生成两条有向无环链表
优化:生成链表主要是为了寻找node1节点的所有父节点,但是对于其中的节点关系没有要求,所以我们可以不使用链表结构,而使用HashSet结构
package binarytree;import java.util.HashMap;
import java.util.HashSet;public class LowestCommonAncester {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public Node lowestCommonAncester(Node head, Node node01, Node node02) {if (head == null) {return null;}HashMap<Node, Node> fatherMap = new HashMap<>();//记录每个节点的父节点,前为子节点,后为父节点fatherMap.put(head, null);//设置头节点的父节点为nullHashSet<Node> set = new HashSet<>();//记录了node01的所有父节点,HashSet集合不保证数据的有序性set.add(node01);//先把node01放进去while (node01 != head) {set.add(fatherMap.get(node01));//把父节点放入set集合中node01 = fatherMap.get(node01);//将node01修改为它的父节点,向上查询}while (node02 != head) {if (set.contains(node02)) {//set集合中存在node02节点向上查询的第一个公共节点即为最低公共节点return node02;}node02 = fatherMap.get(node02);//将node02修改为它的父节点,向上查询}//在node01到头节点的set集合中都没有找到两个节点的公共节点,那么它们一定有个公共节点为头节点return head;}//此方法记录fatherMap集合的数据。即每个节点的父节点public void process(Node node, HashMap<Node, Node> fatherMap) {fatherMap.put(node.left, node);//左孩子的父节点是他自己fatherMap.put(node.right, node);//右孩子的父节点是他自己process(node.left, fatherMap);process(node.right, fatherMap);}
}
方法二:
找到的最低公共节点有三种情况:
node1是两节点的最低公共节点(node1是node2的其中一个父节点)
node2是两节点的最低公共节点(node2是node1的其中一个父节点)
node1和node2无关,两个节点向上查询找到最低公共节点
对于情况一和情况二:当一个节点左右节点一个返回值一个返回空的时候,选择返回值

对于情况三:当一个节点左右都不为空的时候,返回它自己

public Node lowestAncestor(Node node, Node node1, Node node2) {if (node == null || node == node1 || node == node2) {//没有节点或遇到了node1或node2,直接返回当前节点return node;//二叉树最底层的返回,遍历到最底层,或者遇到node1和node2节点}Node left = lowestCommonAncester(node.left, node1, node2);//从左侧返回的node或者nullNode right = lowestCommonAncester(node.right, node1, node2);//从右侧返回的node或者nullif (left != null && right != null) {//当前节点左右返回的值都不为空return node;}return left != null ? left : right;//如果left返回的值为null,就返回右侧right返回的值;如果不是null,返回left的值}
相关文章:
寻找二叉树的最低公共祖先节点
两个节点沿二叉树向上找,找到的第一个公共的节点 例:D和F之间的最低公共节点:B D → B; F → E → B; E和G最低公共节点:A E → B → A; G → C → A; B和F最低公共节点ÿ…...
python网络爬虫(二)基本库的使用urllib/requests
使用urllib 了解一下 urllib 库,它是 Python 内置的 HTTP 请求库,也就是说不需要额外安装即可使用。它包含如下 4 个模块。 request:它是最基本的 HTTP 请求模块,可以用来模拟发送请求。就像在浏览器里输入网址然后回车一样&…...
Kafka快速入门(最新版3.6.0)
文章目录 一、初识MQ1.1 什么是MQ1.2 同步和异步通讯1.1.1 同步通讯1.1.2 异步通讯 1.3 技术对比1.4 MQ的两种模式 二、初识Kafka2.1 Kafka的使用场景2.2 Kafka基本概念2.3 Topic与Partition 三、Kafka基本使用3.1 部署前的准备3.2 启动kafka服务器3.3 Kafka核心概念之Topic3.4…...
CTF/AWD竞赛标准参考书+实战指南:《AWD特训营》
作者简介: 懒大王敲代码,正在学习嵌入式方向有关课程stm32,网络编程,数据结构C/C等 欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖💖 《AWD特训营》 前言 内容简介 读者对象 本书目录 前言…...
从零开始 Spring Cloud 15:多级缓存
从零开始 Spring Cloud 15:多级缓存 多级缓存架构 传统的缓存使用 Redis,大致架构如下: 这个架构存在一些问题: 请求要经过Tomcat处理,Tomcat的性能成为整个系统的瓶颈 Redis缓存失效时,会对数据库产生冲…...
Adobe产品2024
一、软件下载: 二、软件介绍: Adobe公司旗下的产品在影视后期、平面设计等领域有着无可取代的地位。在创意和设计领域中,产品有多达 21 个,包括 Photoshop、Illustrator、InDesign、Premiere Pro、After Effects 和 Acrobat Pro …...
【MySQL】8.0新特性、窗口函数和公用表表达式
文章目录 1. 新增特性2. 移除旧特性2.1 优点2.2 缺点 3. 新特性1:窗口函数3.1 使用窗口函数前后对比3.2 窗口函数分类3.3 语法结构3.4 分类讲解3.4.1 序号函数3.4.1.1 ROW_NUMBER()函数3.4.1.2 RANK()函数3.4.1.3 DENSE_RANK()函数 3.4.2 分布函数3.4.2.1 PERCENT_R…...
华为云云耀云服务器L实例评测|使用clickhouse-benchmark工具对ClickHouse的性能测试
目录 引言 1 ClickHouse简介 2 利用docker安装ClickHouse 2.1 安装Docker 2.2 下载ClickHouse Docker镜像 2.3 创建ClickHouse容器 2.4 访问ClickHouse 3 创建测试表 4 运行 clickhouse-benchmark 5 分析结果 结语 引言 利用华为云的云耀云服务器L实例,…...
枚举最大值+ds:1887D
https://codeforces.com/problemset/problem/1887/D 左边区间最大值小于右边区间最小值 肯定要离线 感觉分治? 枚举左边区间最大值 求出其影响范围,推出左端点可取范围 然后可取右端点就是一段连续大于此值得区间 也就是左端点在一段区间时右端点可…...
模拟最终成绩计算过程
首先输入大于2的整数作为评委人数,然后依次输入每个评委的打分,要求每个分数介于0~100.输入完所有评委打分之后,去掉一个最高分,去掉一个最低分,剩余分数的平均分即为该选手的最终得分 (1) while True:try:n int(input(请输入评委人数:))assert n > 2# 跳出循环breakexce…...
Android10 修改开发者选项中动画缩放默认值
Android 10 修改开发者选项中动画因子默认值 开发者选项中有三个动画因子 “Window animation scale” :窗口动画缩放“Transition animation scale” :过渡动画缩放“Animator duration scale” :动画程序时长缩放 修改默然值 默认3个因子都是1.0,现在修改为默认0.…...
【2023年11月第四版教材】软考高项极限冲刺篇笔记(3)
8 成本管理 成本类型:可变成本、固定成本、直接成本、间接成本、机会成本、沉没成本 应急储备:成本基准内 管理成本:成本基准外 进度偏差:SV,SPI 成本管理主要是规划和控制 成本估算 类比估算 参数估算 自上而下估算 三点估算 备选方案分析 储备分析 质量成本 总资…...
c语言进阶部分详解(详细解析自定义类型——结构体,内存对齐,位段)
上篇文章介绍了一些常用的字符串函数,大家可以去我的主页进行浏览。 各种源码大家可以去我的github主页进行查找:Nerosts/just-a-try: 学习c语言的过程、真 (github.com) 今天要介绍的是:结构体的相关内容 目录 一.结构体类型的声明 1.…...
Mysql第三篇---响应太慢?数据库卡顿?如何优化?
Mysql第三篇—响应太慢?数据库卡顿?如何优化? 统计SQL的查询成本:last_query_cost 一条SQL查询语句在执行前需要确定查询执行计划,如果存在多种执行计划的话,MySQL会计算每个执行计划所需要的成本&#x…...
【计算机网络】HTTP 协议的基本格式以及 fiddler 的用法
HTTP协议的基本格式如下: 1.请求行: 包括请求THHP协议的版本、请求URI(资源路径)和HTTP方法(如GET、POST、PUT、DELETE等) GET/example.html HTTP/1.1 GET表示请求方法,/example.html表示请求的…...
人大金仓与哪吒科技达成战略合作,加快推动智慧港口建设
近日,人大金仓与哪吒港航智慧科技(上海)有限公司(以下简称“哪吒科技”)达成战略合作。双方旨在共享优势资源,联合为港口企业转型升级提供完备的技术支撑与行业解决方案。人大金仓总裁杜胜、哪吒科技总经理…...
FFmpeg工具使用集
FFmpeg工具使用集 About FFmpeg Java调用FFmpeg FFmpeg 工具: FFMPEG 用于转换多媒体文件的 命令行工具 格式之间( ffmpeg\bin\ffmpeg.exe ) ffplay 基于 SDL 和 FFmpeg 库的简单媒体播放器 ( ffmpeg\bin\ffplay.exe ࿰…...
2024级199管理类联考之英语二2200核心词汇(第一天)
define 下定义,定范围definition 定义,清晰度identify 鉴定,识别,确认identifiable 可识别的,可辨认的identity 身份,一致determine 决心,确定determinism 宿命论,决定论judge 判断,法官/裁判behavior 举止,表现behavioral 行为的conduct v-实施,引导,指挥; n-实施方式,行为,举…...
webGL编程指南 第三章 平移三角形 TranslatedTriangle.js
我会持续更新关于wegl的编程指南中的代码。 当前的代码不会使用书中的缩写,每一步都是会展开写。希望能给后来学习的一些帮助 git代码地址 接着 上一节 接着做平移的转化。在本次的案例案例中主要是xy的坐标变量相加,同时传递个给相关变量 <!DOCTY…...
推荐一款支持异步批量下载图片的chrome插件——图片助手(ImageAssistant) 批量图片下载器
https://chrome.google.com/webstore/detail/imageassistant-batch-imag/dbjbempljhcmhlfpfacalomonjpalpko/related?hlzh-CNhttps://chrome.google.com/webstore/detail/imageassistant-batch-imag/dbjbempljhcmhlfpfacalomonjpalpko/related?hlzh-CN 安装后直接点击 会根据…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
相关类相关的可视化图像总结
目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系,可直观判断线性相关、非线性相关或无相关关系,点的分布密…...
对象回调初步研究
_OBJECT_TYPE结构分析 在介绍什么是对象回调前,首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例,用_OBJECT_TYPE这个结构来解析它,0x80处就是今天要介绍的回调链表,但是先不着急,先把目光…...
