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

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

例: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 安装后直接点击 会根据…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
