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

算法刷题Day15: BM37 二叉搜索树的最近公共祖先

题目链接

描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

思路

  1. 从高度着手,父节点的高度肯定大于等于两个节点p、q的高度;
  2. 从高度相同的两个节点,一起往上走,相遇点即为父节点。

先找到p、q当前节点,高度较低的节点指针然后不断向上遍历,直到两个指针同一高度。同一高度之后,再同时向上遍历,直到相遇。

代码

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
class NewDot:def __init__(self,x):self.val = xself.h = 0self.left = Noneself.right = Noneself.pre = None
#建树,记录父节点,以及当前节点的高度
def build_new_tree(root:TreeNode, height):if root:new_dot = NewDot(root.val)new_dot.h = height + 1new_left = build_new_tree(root.left,height + 1)new_right = build_new_tree(root.right,height + 1)new_dot.left = new_leftnew_dot.right = new_rightif new_left:new_left.pre = new_dotif new_right:new_right.pre = new_dotreturn new_dotelse:return None
# 给一个值,递归找到当前节点
def search_node(root:NewDot,val):if root:return rootif root.val == val:return rootleft_node = search_node(root.left,val)if left_node:return left_nodeelse:return search_node(root.right,val)class Solution:def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:# 建新树new_dot = build_new_tree(root,0)# 找到两个节点位置low_node = search_node(new_dot,p)high_node = search_node(new_dot,q)# 往上遍历,使两者处于同一高度if low_node.h < high_node.h:low_node, high_node = high_node,low_nodediff_h = low_node.h - high_node.hwhile diff_h:low_node = low_node.prediff_h -= 1while low_node != high_node:low_node = low_node.prehigh_node = high_node.prereturn low_node.val

看着大佬手撕之后,自己回去重新手撕一遍。这道题有两个基本功,一是,重新建一棵树,每个节点保存其父节点以及该节点的高度。二是,根据val值定位某个节点,使用递归,注意回传找到的节点。今天学习到了好多~ 开心~

相关文章:

算法刷题Day15: BM37 二叉搜索树的最近公共祖先

题目链接 描述 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q&#xff0c;最近公共祖先LCA(T,p,q)表示一个节点x&#xff0c;满足x是p和q的祖先且x的深度尽可能大。在这里&#xff0c;一个节点也可以…...

正则表达式去除文本中括号()<>[]里的内容

一行文本中包含有各种括号&#xff0c;如()、<>、[]&#xff0c;我们希望把括号及括号内的内容0去除&#xff0c;可以通过正则表达式来实现。 匹配() pattern r\([^)]*\) # 匹配()匹配一个左括号(&#xff0c;然后匹配0个或多个不是右括号的任意字符[^)]*&#xff0c…...

Environment Modules安装配置

Environment Modules安装配置 Environment Modules是一款用来管理计算机软件环境的软件&#xff0c;通过简单的命令来控制计算机环境变量。本文接受该软件的安装和配置方法 系统&#xff1a; Linux OpenSUSE 15.6 软件版本&#xff1a; modules 5.5 依赖&#xff1a; gcc 7.5…...

constexpr、const和 #define 的比较

constexpr、const 和 #define 的比较 一、定义常量 constexpr 定义&#xff1a;constexpr用于定义在编译期可求值的常量表达式。示例&#xff1a;constexpr int x 5;这里&#xff0c;x的值在编译期就确定为5。 const 定义&#xff1a;const表示变量在运行期间不能被修改&…...

STM32串口接收与发送(关于为什么接收不需要中断而发生需要以及HAL_UART_Transmit和HAL_UART_Transmit_IT的区别)

一、HAL_UART_Transmit和HAL_UART_Transmit_IT的区别 1. HAL_UART_Transmit_IT&#xff08;非阻塞模式&#xff09;&#xff1a; HAL_UART_Transmit_IT 是非阻塞的传输函数&#xff0c;也就是说&#xff0c;当你调用 HAL_UART_Transmit_IT 时&#xff0c;它不会等到数据完全发…...

如何制作“优美”PPT

目录 1.免费PPT模板网站&#xff1a; 2.免费有较好质量的图片网站&#xff1a; 免费图片资源 免费透明PNG图片资源&#xff1a; 免费icon图片资源&#xff1a; 3.选择好的图片&#xff1a; 图片底色 4.要与不要 千万不要&#xff1a; 一定要&#xff1a; 6.一些建议…...

5G模组AT命令脚本-控制模组进入飞行模式

控制模组进入飞行模式 控制模组进入飞行模式 控制模组进入飞行模式 控制模组进入飞行模式 #!/bin/bash ## 5G模组采用USB3.0与上位机连接&#xff0c;usb接口在上位机上虚拟出多个port,其中一个可用于发送AT命令&#xff0c;控制模组 ## 本脚本控制模组进入飞行模式## flyin …...

计算机网络-Wireshark探索ARP

使用工具 Wiresharkarp: To inspect and clear the cache used by the ARP protocol on your computer.curl(MacOS)ifconfig(MacOS or Linux): to inspect the state of your computer’s network interface.route/netstat: To inspect the routes used by your computer.Brows…...

Vue 2 生命周期函数详解

Vue 2 生命周期函数详解 引言 Vue.js 是一个渐进式的 JavaScript 框架&#xff0c;用于构建用户界面。理解 Vue 的生命周期函数&#xff08;Lifecycle Hooks&#xff09;对于开发高效的 Vue 应用至关重要。本文将详细介绍 Vue 2 的生命周期钩子、每个阶段的作用及其代码示例&…...

Vue的路由实现模式:hash模式和history模式

Vue 路由的两种模式&#xff1a; hash 模式&#xff1a; 类似于住在一个大房子里&#xff0c;你的地址很长&#xff0c;但用一个 “门牌号”&#xff08;# 后面的部分&#xff09;来标识你住哪间房间。 例如&#xff1a; bash http://example.com/#/home 这就好比 “example.…...

R语言 | 峰峦图 / 山脊图

目的&#xff1a;为展示不同数据分布的差异。 1. ggplot2 实现 # 准备数据 datmtcars[, c("mpg", "cyl")] colnames(dat)c("value", "type") head(dat) # value type #Mazda RX4 21.0 6 #Mazda RX4 Wag …...

Kubernetes(K8s)

头条&#xff1a;参考资料 Kubernetes 入门指南&#xff1a;从基础到实践_kubernetes 从入门到实践-CSDN博客 Kubernetes&#xff08;k8s&#xff09;与docker的区别 Docker、Kubernetes之间的区别_docker和kubernetes区别-CSDN博客 Docker部署SpringBoot项目&#xff08;镜…...

【代码随想录|贪心算法05】

56.合并区间 题目链接56. 合并区间 - 力扣&#xff08;LeetCode&#xff09; 这道题思路跟前两道也很像&#xff0c;就是更新把相同的区间合并而已。 class Solution { public: static bool cmp(const vector<int>& a,const vector<int>& b){return a[0…...

QQ聊天室--C++基础项目--QT+Socket网络编程

目录 一、项目概述 二、项目成果 1、QQ基础界面展示&#xff1a; 2、群聊界面展示&#xff1a; 3、聊天功能展示 三、项目代码 1、登录头文件&#xff08;denglu.h&#xff09; 2、登录源文件&#xff08;denglu.cpp&#xff09; 3、聊天界面头文件&#xff08;widget.…...

分布式搜索引擎之elasticsearch基本使用2

分布式搜索引擎之elasticsearch基本使用2 在分布式搜索引擎之elasticsearch基本使用1中&#xff0c;我们已经导入了大量数据到elasticsearch中&#xff0c;实现了elasticsearch的数据存储功能。但elasticsearch最擅长的还是搜索和数据分析。 所以j接下来&#xff0c;我们研究下…...

今日商协丨商协会在“双循环”新发展格局中的作用

在当今全球经济环境中&#xff0c;世界格局正在经历深刻变化&#xff0c;中国正在全面构建“双循环”新发展格局&#xff0c;以实现更高质量、更可持续的发展。在这一过程中&#xff0c;商协会发挥着不可或缺的作用。 商协会在国内大循环中扮演促进者的角色&#xff0c;不仅活…...

前端项目安装node-sass

这个依赖比较难装&#xff0c;因为这个依赖需要安装的版本是和node版本绑定的&#xff0c;所以你需要去sass的官网找到对应关系&#xff0c;下面是我的版本信息&#xff1a; node 16.14.2 node-sass:^6.0.1 sass-loader:^10.2.0 "sass": "^1.82.0", 你…...

算法-字符串-678.有效的括号字符串

一、题目 二、思路解析 1.思路&#xff1a; 用leftMin变量来记录存在的“&#xff08;”&#xff0c; 用leftMax变量记录字符串中最多的“&#xff08;” 2.常用方法&#xff1a; 无 3.核心逻辑&#xff1a; 1.遍历字符串&#xff1a; a.当前字符为"("&#xff0c;le…...

linux 压缩文件为zip

在 Linux 系统中&#xff0c;可以使用 zip 命令来压缩文件或目录 打开终端&#xff08;Terminal&#xff09;。 使用 cd 命令导航到要压缩的文件或目录所在的路径。 运行以下命令来压缩文件或目录&#xff1a; 压缩单个文件&#xff1a; zip output.zip file.txt这里&#xf…...

Cisco Packet Tracer | Cisco Packet Tracer - VLAN 实验 - 交换机的 VLAN 划分

关注这个工具的其它相关笔记&#xff1a;Cisco Packet Tracer —— 使用教程合集-CSDN博客 0x01&#xff1a;VLAN 划分 - 单个交换机 0x0101&#xff1a;拓扑搭建流程 从软件底部拖出一台交换机&#xff08;笔者选择的型号是 2960 IOS15&#xff09;&#xff1a; 然后再拖出四…...

《计算机网络》(408大题)

2009 路由转发和静态路由的计算 子网划分、路由聚合的计算 注&#xff1a;CIDR中的子网号可以全为0或1&#xff0c;但是其主机号不允许。 注&#xff1a; 这里其实是把到互联网的路由当做了一个默认路由&#xff08;当一个目的网络地址与路由表中其他都不匹配时&#xff0c;…...

二叉树概述

目录 一、二叉树的基本结构 二、二叉树的遍历 1.前序 2.中序 3.后序 4.层序遍历 三.计算二叉树的相关参数 1.计算节点总个数 2.计算叶子节点的个数 3.计算树的高度 4.计算第k层的子树个数 5.查找树中val为x的节点 四.刷题 1.单值二叉树 2.检查两棵树是否相同 3.一…...

qiankun学习记录

什么是微前端 微前端是指存在于浏览器中的微服务&#xff0c;其借鉴了微服务的架构理念&#xff0c;将微服务的概念扩展到了前端。 如果对微服务的概念比较陌生的话&#xff0c;可以简单的理解为微前端就是将一个大型的前端应用拆分成多个模块&#xff0c;每个微前端模块可以…...

【C++ 20进阶(2):初始化 Initializer

【C 20进阶&#xff08;2&#xff09;&#xff1a;初始化 Initializer】 原文&#xff1a;https://blog.csdn.net/weixin_44259356/article/details/144377955 引言 本篇文章为系列文章将着重介绍C20新特性&#xff0c;一是希望可以和大家交流分享&#xff0c;二是也便于自己…...

vue3学习——事件监听(v-on)

我们可以使用 v-on 指令监听 DOM 事件&#xff1a; <button v-on:click"increment">{{ count }}</button> 因为其经常使用&#xff0c;v-on 也有一个简写语法&#xff1a; <button click"increment">{{ count }}</button> 此处…...

java全栈day13-后端Web实战2

接上述查询部门实现&#xff0c;完成后续要求 一、统一响应结果 1.1步骤 资料如下 对一开始的代码修改如下 结果如下 1.2测试 指定请求方式 结果 小结 二、前后端联调测试 资料如下&#xff1a; (不行&#xff0c;一定要不带空格和不带中文&#xff0c;要不然启动不了试了半天…...

C++/CX,一个智能的 C++/Windows 平台开发库!

以下是一篇关于C/CX的C学习文章&#xff1a; 开篇 嘿&#xff0c;大家好呀&#xff01;我是一行。今天咱们来一起探索一个超棒的C开发库——C/CX&#xff0c;它可是在Windows平台开发中非常智能且强大的工具哦&#xff0c;能让我们的开发变得更加高效便捷。让我们一起开启今天的…...

分布式 分布式事务 总结

前言 相关系列 《分布式 & 目录》《分布式 & 分布式事务 & 总结》《分布式 & 分布式事务 & 问题》 分布式事务 所谓分布式事务是指操作范围笼罩多个不同节点的事务。例如对于订单节点&库存节点而言&#xff0c;一次完整的交易需要同时调动两个节…...

数据结构(3)单链表的模拟实现

上一节我们进行了数据结构中的顺序表的模拟式现&#xff0c;今天我们来实现一下另外一个数据结构&#xff1a;单链表。 我们在实现顺序表之后一定会引发一些问题和思考&#xff1a; 1.顺序表在头部和中间插入数据会用到循环&#xff0c;时间复杂O&#xff08;N&#xff09; …...

HBU深度学习实验14.5-循环神经网络(1.5)

梯度爆炸实验 造成简单循环网络较难建模长程依赖问题的原因有两个&#xff1a;梯度爆炸和梯度消失。一般来讲&#xff0c;循环网络的梯度爆炸问题比较容易解决&#xff0c;一般通过权重衰减或梯度截断可以较好地来避免&#xff1b;对于梯度消失问题&#xff0c;更加有效的方式…...

Redis01

springbootredis 特点 1.高效性 2.支持多种数据结构 String,list,set,hash.zset 3.稳定性&#xff1a;持久化&#xff0c;主从复制&#xff08;集群&#xff09; 4.其他特性&#xff1a;支持过期时间&#xff0c;支持事务&#xff0c;消息订阅。 安装 1.下载安装包 redis官…...

数据库中decimal、float 和 double区别

在计算机科学中&#xff0c;decimal、float 和 double 是用于表示和处理数值的不同数据类型。 - decimal 是一种精确的十进制浮点数表示&#xff0c;通常用于需要高精度计算的场景&#xff0c;比如财务应用。它能够精确表示小数&#xff0c;并且不会出现浮点数运算误差。 - flo…...

HDR视频技术之五:HDR生产流程

在介绍 HDR 的生产流程之前&#xff0c;我们先介绍下视频制作与传输的一些基本知识。 内容类型&#xff1a; 直播内容&#xff08; live content&#xff09; ——所谓的直播内容即没有后处理过程以及创作者意图。分发给用户的信息是实时产生并且实时制作并派发的。常见的应用…...

CTFshow-爆破(Web21-28)

CTFshow-爆破(Web21-28) Web21 抓包 选则dic.zip里的字典爆破&#xff0c;记得添加前缀admin: 答案admin:shark63 burp里有一个自定义迭代器&#xff0c;可以设置前几部分&#xff0c;很好用 Web22 题目失效了直接看wp吧 360quake 使用空间搜索引擎—>360quake 搜索语法…...

C++重点和练习

作业题目&#xff1a; #include <iostream> using namespace std; class Rec {const int length;int width; public:void set_length(int l);void set_width(int w);int get_length();int get_width();void show(); };#include <iostream> using namespace std; c…...

UnityShaderLab-实现溶解效果

实现思路&#xff1a; 使用一张噪声图&#xff0c;与一个Cut值计算&#xff08;加或减&#xff09;&#xff0c;将计算后的值赋值给Alpha,然后小于0的片段就被丢弃掉了。 ShaderGraph实现&#xff1a; ShaderLab实现&#xff1a; Shader "Dissolve" {Properties{_…...

SQLite 数据库学习

1.install sudo apt update sudo apt install sqlitebrowser这是一个开源的图形用户界面工具&#xff0c;专门用于开发、管理和分析 SQLite 数据库。它支持创建或导入导出表、编辑数据、执行 SQL 查询等功能。 2.python 操作数据库 Python 内置了 sqlite3 模块&#xff0c;使…...

【LeetCode: 463. 岛屿的周长 + bfs】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

Bean的注入、单例和多例

目录 注入Bean对象 属性注入 构造注入 属性注入专题 注入集合/数组 级联简单类型赋值 Bean的单例和多例 注入Bean对象 简单类型使用value(除Date)&#xff0c;非简单类型使用ref 属性注入 name规则&#xff1a;必须提供set方法&#xff0c;去掉set&#xff0c;第一个字…...

java 使用JSqlParser和CCJSqlParser 解析sql

maven <dependency><groupId>com.github.jsqlparser</groupId><artifactId>jsqlparser</artifactId><version>4.9</version> </dependency>解析SQL String sql "select aa,bb from b"; Statement statementCCJSq…...

Anaconda Conda Pip 的区别与联系

在Python生态中,Anaconda、Conda和Pip是三个非常重要的工具,它们在包管理和环境管理方面发挥着关键作用。 Anaconda Anaconda是一个为科学计算而设计的Python发行版,它集成了Conda、Python以及大量的数据科学相关库,如NumPy、Pandas等。Anaconda的主要优势在于它提供了一个…...

总结的一些MySql面试题

目录 一&#xff1a;基础篇 二&#xff1a;索引原理和SQL优化 三&#xff1a;事务原理 四&#xff1a;缓存策略 一&#xff1a;基础篇 1&#xff1a;定义&#xff1a;按照数据结构来组织、存储和管理数据的仓库&#xff1b;是一个长期存储在计算机内的、有组织的、可共享 的…...

【实验15】LSTM的记忆能力实验

目录 1 模型构建 1.1 LSTM层 1.1.1 自定义LSTM算子 1.1.2 nn.LSTM 1.1.3 将自定义LSTM与pytorch内置的LSTM进行对比 1.2 模型汇总 2 模型训练 2.1 训练指定长度的数字预测模型 2.2 多组训练 2.3 损失函数展示 3 模型评价 4 完整代码 5 LSTM模型门状态和单元状态的…...

SSH克隆github项目

1、生成密钥 ssh-keygen -t rsa -C "你的邮箱xxx.com" 全程回车即可&#xff08;不用输入ras文件名及密码&#xff09;、为了方便下面的公钥查看 2、配置公钥 查看公钥内容 cat c:\Users\xxx\.ssh\id_rsa.pub(修改为自己的路径及名字) 将公钥内容复制并粘贴至…...

计算机网络ENSP课设--三层架构企业网络

本课程设计搭建一个小型互联网&#xff0c;并模拟Internet的典型Web服务过程。通过此次课程设计&#xff0c;可以进一步理解Internet的工作原理和协议过程&#xff0c;并提高综合知识的运用能力和分析能力。具体目标包括&#xff1a; &#xff08;1&#xff09;掌握网络拓扑的…...

Node.js系统模块

【图书介绍】《Node.jsMongoDBVue.js全栈开发实战》-CSDN博客 《Node.jsMongoDBVue.js全栈开发实战&#xff08;Web前端技术丛书&#xff09;》(邹琼俊)【摘要 书评 试读】- 京东图书 (jd.com) 2.2.1 什么是系统模块 由于Node.js运行环境提供的API都是以模块化的方式进行开…...

React - useActionState、useFormStatus与表单处理

参考文档&#xff1a;react18.3.1官方文档 一些概念&#xff1a; React 的 Canary 和 Experimental 频道是 React 团队用于发布和测试新功能的渠道。 useActionState useActionState 是一个可以根据某个表单动作的结果更新 state 的 Hook。 const [state, formAction, isPe…...

GC常见垃圾回收算法,JVM分代模型

如何判断是垃圾&#xff1f;引用计数器和Root可达性算法 如何进行清除&#xff1f;标记清除、复制、标记整理 堆分代模型&#xff1f;Eden&#xff0c;Surevivor&#xff0c;Tenuring 一个对象从创建到消亡的过程&#xff1f; 对象什么时候进入老年代&#xff1f; 一、GC&a…...

深入探索 JVM:原理、机制与实战

一、JVM 概述 JVM&#xff08;Java Virtual Machine&#xff09;是 Java 程序运行的核心组件&#xff0c;它提供了一个独立于硬件和操作系统的执行环境&#xff0c;使得 Java 程序能够在不同平台上具有跨平台的特性。 JVM 主要由以下几部分组成&#xff1a; 类装载器&#xf…...

前端成长之路:HTML(2)

HTML中有两个非常重要的标签——表格和表单&#xff0c;在介绍之前需要先了解表格和表单的区别&#xff1a;表格是用于展示数据的&#xff1b;表单是用于提交数据的。本文主要介绍表格。 表格标签 表格主要是用于显示、展示数据的&#xff0c;并非是页面布局。它可以使本来难…...