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

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...