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

LeetCode236.最近的公共祖先

在这里插入图片描述

求解最近公共祖先的算法

分为两个步骤:

  1. 求出两节点路径
  2. 取两路径上最后一个相同的节点(该节点即为p,q节点的最近公共祖先)

节点路径的算法设计与实现

求节点路径即输入二叉树根节点与待求节点返回根节点到该节点路径上的所有节点。

具体有如下几个要点:

  1. 我们需要设置一个栈,存储最终的节点路径。找到该节点时,从栈底到栈顶存储的节点即为从根节点到该节点的路径。
    在这里插入图片描述
  2. 需要通过遍历算法,从根节点遍历至该节点。树的遍历算法可以是递归的深度优先搜索算法。找到该节点后就结束搜索。
    在这里插入图片描述
  3. 将遍历过程中遇到的节点按照顺序存储到栈中。节点遍历完成之后需要弹出栈,从而保证栈中存储的节点时根节点到当前遍历节点路径上的节点。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

具体代码

深度优先搜索寻找路径上的节点

在这里插入图片描述

利用两节点的路径寻找最近公共祖先

在这里插入图片描述
在这里插入图片描述

测试主程序

在这里插入图片描述
在这里插入图片描述
参考资料
算法与数据结构,二叉树,程序员面试高频题,最近的公共祖先

相关文章:

LeetCode236.最近的公共祖先

求解最近公共祖先的算法 分为两个步骤: 求出两节点路径取两路径上最后一个相同的节点(该节点即为p,q节点的最近公共祖先) 节点路径的算法设计与实现 求节点路径即输入二叉树根节点与待求节点返回根节点到该节点路径上的所有节…...

【springcloud 微服务】Spring Cloud Alibaba整合Sentinel详解

目录 一、前言 二、环境准备 2.1 部署sentinel管控台 2.1.1 官网下载sentinel的jar包 2.1.2 启动控制台 2.1.3 访问控制台 2.2 整合springcloud-alibaba 2.2.1 引入相关依赖 2.2.2 修改配置文件 2.2.3 增加一个测试接口 2.2.4 接口测试 三、sentinel 流控规则使用 …...

ASP医院管理系统—病历管理系统的设计与实现

病历管理系统是医院管理系统的重要组成,该系统的开发主要包括后台数据库的建立以及前台应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的数据库,而对于后者则要求具有齐全完善的应用程序功能,友好人性化的操作界面。该系统采用现代的办公自动化…...

【蓝桥杯】动态规划(dp)入门!| 入门动态规划的正确方式! ——学习笔记

目录 最暴力的dfs --> 记忆化搜索 ---> 递推(dp) 记忆化搜索 暴力dfs 记录答案 递推的公式 dfs 向下递归的公式 递推数组的初始值 递归的边界 动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili 大佬教学视频…...

元宇宙与网络安全

元宇宙是一种虚拟现实空间,用户可以在计算机生成的环境中进行互动。元宇宙的应用范围很广,比如房地产,医疗,教育,军事,游戏等等。它提供了更具沉浸感的体验,更好地现实生活整合,以及…...

Pod控制器之hpa

简述 HPA全称HorizontalPodAutoscaler Pod水平自动扩缩容,Kubernetes控制器HPA是一种用于自动调整Pod数量的控制器。它可以根据资源使用情况自动增加或减少Pod的数量,以确保应用程序的高可用性和性能。HPA可以根据CPU使用率或自定义指标来进行调整&…...

发现一个白嫖GPT4.0的方法!真的是完胜3.5!

大家好,我是五竹。 先说个基本的科普,最近被问的人都嘛了。 1、ChatGPT账号只有两种:普通账号和plus账号。 2、普通账号升级到plus账号,需要绑定国外的支付方式,每个月大概130左右!plus账号更稳!更快&am…...

数据结构之第四章、ArrayList和顺序表

一、线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是…...

webase全家桶搭建教程过程记录+bug解决

前置条件 Ubuntu20 基础环境搭建 检查Java java -version 检查mysql(Ubuntu部署MySQL) mysql --version 在装MySQL的时候发现了一个问题 就是不管怎么sudo mysql_secure_installation,,第二步设置密码就是不对,解…...

openEuler Linux 部署 HadoopHA

openEuler Linux 部署 HadoopHA 升级操作系统和软件 yum -y update升级后建议重启 安装常用软件 yum -y install gcc gcc-c autoconf automake cmake make rsync vim man zip unzip net-tools zlib zlib-devel openssl openssl-devel pcre-devel tcpdump lrzsz tar wget修改…...

React-Hooks----useEffect()

文章目录前言用法前言 useEffect() 是 React 中最常用的 Hook 之一,它可以让函数组件拥有类似于类组件中 componentDidMount、componentDidUpdate 和 componentWillUnmount 生命周期函数的功能。 用法 useEffect() 接受两个参数 第一个参数是一个函数&#xff0c…...

JavaWeb基础-汇总

SSM框架课程汇总01-MySQL基础02-MySQL高级03-JDBC04-JDBC练习05-Maven&Mybatis基础06-Mybatis练习07-JavaScript08-Web概述09-HTTP10-Tomcat11-Servlet12-Request&Response13-用户注册登录案例14-JSP15-JSP案例16-会话技术17-用户登录注册案例18-Filter19-Listener&…...

Niuke:JZ36.二叉树与双向链表

文章目录Niuke:JZ36.二叉树与双向链表题目描述示例思路分析代码实现Niuke:JZ36.二叉树与双向链表 题目描述 描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示 注意: 1.要求不能创建任何新的结点,只…...

javaScript---读懂promise、async/await

一、Promise Promise 是一个 Es 6 提供的类,目的是更加优雅地书写复杂的异步任务。可以解决嵌套式的回调地域问题,Promise 将嵌套格式的代码变成了顺序格式的代码。 //回调地域 setTimeout(function () {console.log("红灯");setTimeout(function () {console.lo…...

【Linux】TCP编程流程

TCP编程流程 socket()创建套接字,套接字TCP协议选择流式服务SOCK_STREAM。 bind()指定套接字使用的IP地址和端口。IP地址是自己主机地址,端口为一个16位的整形值。 listen()方法创建监听队列。监听队列分为存放未完成三次握手的连接和完成三次握手的连…...

SuperMap iDesktop 下载安装,生成本地瓦片,以及发布本地瓦片服务

SuperMap iDesktop 是插件式桌面GIS软件,提供基础版、标准版、专业版和高级版四个版本,具备二三维一体化的数据处理、制图、分析、海图、二三维标绘等功能,支持对在线地图服务的无缝访问及云端资源的协同共享,可用于空间数据的生产…...

【ONE·Data || 常见排序说明】

总言 数据结构基础:排序相关内容。    文章目录总言1、基本介绍2、插入排序2.1、直接插入排序:InsertSort2.1.1、单趟2.1.2、总趟2.2、希尔排序(缩小增量排序):ShellSort2.2.1、预排序1.0:单组分别排序2.…...

本节作业之跟随鼠标的天使、模拟京东按键输入内容、模拟京东快递单号查询

本节作业之跟随鼠标的天使、模拟京东按键输入内容、模拟京东快递单号查询1 跟随鼠标的天使2 模拟京东按键输入内容3 模拟京东快递单号查询1 跟随鼠标的天使 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><met…...

ChatGPT 被大面积封号,到底发生什么了?

意大利数据保护机表示 OpenAI 公司不但非法收集大量意大利用户个人数据&#xff0c;没有设立检查 ChatGPT 用户年龄的机制。 ChatGPT 似乎正在遭遇一场滑铁卢。 3月31日&#xff0c; 大量用户在社交平台吐槽&#xff0c;自己花钱开通的 ChatGPT 账户已经无法登录&#xff0c;更…...

教你精通JavaSE语法之第十一章、认识异常

一、异常的概念与体系结构 1.1异常的概念 在Java中&#xff0c;将程序执行过程中发生的不正常行为称为异常。比如之前写代码时经常遇到的&#xff1a; 1.算术异常 System.out.println(10 / 0); // 执行结果 Exception in thread "main" java.lang.ArithmeticExcep…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...