代码随想录算法训练营第十八天| 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
题目:
530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点
root,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3] 输出:1示例 2:
输入:root = [1,0,48,null,null,12,49] 输出:1
思路:
1.直接法,中序遍历将元素压入数组,此时得到从小到大排列的数组,再求数组中差值最小的值
2.双指针法,中序递归,pre指向当前节点的前一个节点,比较pre和cur的值,不断更新差值最小的值
算法:
//双指针法
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func getMinimumDifference(root *TreeNode) int {minV := math.MaxInt //初始化为无穷大// minV := int(^uint(0)>>1) 另一种初始化方法var pre *TreeNode //记录前一个节点var travelsal func(node *TreeNode)travelsal = func(node *TreeNode) {if node == nil {return}//左travelsal(node.Left)//中if pre != nil {minV = min(minV, node.Val-pre.Val)}pre = node//右travelsal(node.Right)}travelsal(root)return minV}
//法二,直接法
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func getMinimumDifference(root *TreeNode) int {//中序遍历压入数组,再比较数组差值tmpArr := make([]int, 0)var traversal func(node *TreeNode)traversal = func(node *TreeNode) {if node == nil {return}traversal(node.Left)tmpArr = append(tmpArr,node.Val)traversal(node.Right)}traversal(root)//minv要初始化为最大值minv := math.MaxIntfor i := 1; i < len(tmpArr); i++ {minv = min(minv, tmpArr[i]-tmpArr[i-1])}return minv}
注意:
1.初始化int的最大值有两种方式,一种是int(^uint(0)>>1)
^uint(0)产生uint类型的全 1(二进制表示为全 1 的值)。^uint(0) >> 1将所有位右移一位,相当于将最高位的 1 变成了 0,从而得到uint类型的最大值的一半。
2.另一种是直接调用math函数:math.MaxInt
题目:
501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树(BST)的根节点
root,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2] 输出:[2]示例 2:
输入:root = [0] 输出:[0]提示:
- 树中节点的数目在范围
[1, 104]内-105 <= Node.val <= 105
思路:
1. 直接法,中序遍历,使用map记录每个元素出现次数,找出map中的众数,再将出现次数=众数的元素全部返回
算法:
//方法一:直接法
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func findMode(root *TreeNode) []int {//直接法,map存储元素的出现次数mm := make(map[int]int, 0)var traversal func(node *TreeNode)traversal = func(node *TreeNode) {if node == nil {return}//中序遍历将元素的出现次数计入maptraversal(node.Left) //左mm[node.Val]++ //中traversal(node.Right) //右}traversal(root)//res数组存最终结果res := make([]int, 0)x := 0//求众数for _, v := range mm {fmt.Printf("x=%d,v=%d",x, v)x = max(x, v)}//将众数的值加入数组,返回数组for k, v := range mm {if v == x {res = append(res, k)}}return res
}
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func findMode(root *TreeNode) []int {//双指针法var pre *TreeNodecount, maxcount := 0, 0res := make([]int, 0)var taversal func(node *TreeNode)taversal = func(node *TreeNode){if node == nil {return}taversal(node.Left)if pre == nil {count=1} else if node.Val == pre.Val{count++} else {count = 1}pre = node//注意频率相等收获元素if count == maxcount {res = append(res, node.Val)}if count > maxcount {//清空resres = []int{}res = append(res, node.Val)maxcount = count}taversal(node.Right)}taversal(root)return res}
注意:
题目:
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点5和节点1的最近公共祖先是节点3 。示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3:
输入:root = [1,2], p = 1, q = 2 输出:1提示:
- 树中节点数目在范围
[2, 105]内。-109 <= Node.val <= 109- 所有
Node.val互不相同。p != qp和q均存在于给定的二叉树中。
思路:
1、自底向上查找,这样就可以找到公共祖先,二叉树回溯的过程就是从低到上
2、后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑
算法:
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil {return nil}if root == p || root == q {return root}left := lowestCommonAncestor(root.Left,p,q)right := lowestCommonAncestor(root.Right,p,q)if left != nil && right != nil {// p 和 q 分别在 root 的左右子树中,所以 root 是最低共同祖先return root}if left != nil {// p 和 q 都在 root 的左子树中,或者其中一个就是 leftreturn left}if right != nil {// p 和 q 都在 root 的右子树中,或者其中一个就是 rightreturn right}// p 和 q 都不在 root 的子树中return nil
}
注意:
相关文章:
代码随想录算法训练营第十八天| 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先
题目: 530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 输入:root [4,2,6,1,3] 输出:…...
会议室占用的时间(75%用例)D卷(JavaPythonC++Node.jsC语言)
现有若干个会议,所有会议共享--个会议室,用数组表示各个会议的开始时间和结束时间,格式为: 会议1开始时间,会议1结束时间 会议2开始时间,会议2结束时间 请计算会议室占用时间段。 输入描述: 第一行输入一个整数 n,表示会议数量 之后输入n行,每行两个整数,以空格分隔,…...
C++初阶_1:namespace
本章详细解说:namespace 。 namespace: namespace,意为:命名空间,c的关键字(关键字,就是提示:取变量名,函数名时不能与之撞名)。 namespace的价值: 为了解…...
低代码开发平台:效率革命还是质量隐忧?
如何看待“低代码”开发平台的兴起? 近年来,“低代码”开发平台如雨后春笋般涌现,承诺让非专业人士也能快速构建应用程序。这种新兴技术正在挑战传统软件开发模式,引发了IT行业的广泛讨论。低代码平台是提高效率的利器࿰…...
在 Django 表单中传递自定义表单值到视图
在Django中,我们可以通过表单的初始化参数initial来传递自定义的初始值给表单字段。如果我们想要在视图中设置表单的初始值,可以在视图中创建表单的实例时,传递一个字典给initial参数。 1、问题背景 我们遇到了这样一个问题:在使…...
Android之复制文本(TextView)剪贴板
效果图: 功能简单就是点击“复制”,将邀请码复制到 剪贴板中 布局 <androidx.constraintlayout.widget.ConstraintLayoutandroid:id"id/clCode"android:layout_width"dimen/dp_0"android:layout_height"dimen/dp_49"…...
Ubuntu24.04设置国内镜像软件源
参考文章: Ubuntu24.04更换源地址(新版源更换方式) - 陌路寒暄 一、禁用原来的软件源 Ubuntu24.04 的源地址配置文件发生改变,不再使用以前的 sources.list 文件,升级 24.04 之后,该文件内容变成了一行注…...
分布式与微服务详解
1. 单机架构 只有一台机器,这个机器负责所有的工作 (这里假定一个电商网站) 现在大部分公司的产品都是单机架构 。 2. 分布式架构 一台机器的硬件资源是有限的,服务器处理请求是需要占用硬件资源的,如果业务增长&a…...
Vue设置滚动条自动保持到最底端
需求描述:在开发中我们常常会遇到需要让滚动条保持到最底端的需求,比如在开发一个聊天框时,请求接口拿到消息列表数据,展示到前端页面时,需要让滚动条自动滚到最底端,以此来展示最后的聊天记录。同时&#…...
uniapp创建一个新项目并导入uview-plus框架
近年来,随着技术的发展,人们越来越意识到跨平台和统一的重要性。对于同一款应用来说,一般都会有移动端、PC端、甚至小程序端。这是由于设备的不同,我们必须要做很多的客户端来满足不同的用户需求。但是由于硬件设施的不同…...
LabVIEW光电在线测振系统
开发了一种基于LabVIEW软件和光电技术的在线测振系统。该系统利用激光作为调制光源,并通过位置敏感型光电传感器(PSD)进行轴振动的实时检测。其主要特点包括非接触式测量、广泛的测量范围、高灵敏度和快速响应时间,且具备优良的抗…...
分布式光伏电站 转化能源 丰富用电结构
分布式光伏系统是一种利用分散式的可再生能源,在靠近用户端的地方安装光伏发电设施,通过光伏效应将太阳能转化为直流电能,并通过逆变器将其转换为交流电,以供用户使用的系统。以下是对分布式光伏系统的详细阐述: 一、…...
环境配置:如何在IntelliJ IDEA中安装和修改JDK版本配置(以Windows为例)
环境配置:如何在IntelliJ IDEA中安装和修改JDK版本配置(以Windows为例) 为了在Java开发中使用最新的功能和优化,升级和配置JDK版本是必不可少的。本文将详细介绍如何下载、安装、配置最新的JDK版本,并在IntelliJ IDEA…...
Spring AOP 原理——代理模式
目录 一、代理模式 1.1 静态代理 1.2 动态代理 1.2.1 JDK动态代理 1.2.2 CGLIB动态代理 Spring AOP 是基于动态代理来实现AOP的。 一、代理模式 代理模式, 也叫委托模式。该模式是为其他对象提供⼀种代理以控制对这个对象的访问。它的作用就是通过提供一个代理类&#…...
leetcode 234.回文链表
思路:其实就是判断反转链表是不是和原链表一样的问题。 我们可以借助反转链表的思路,首先我们先把链表的全部元素正向存储,然后再把链表进行反转。 之后我们再遍历反转之后的链表结点元素是不是和刚刚存储数组里面的元素一致就可以了。一旦…...
AD中Split Planes 的作用和功能
在 Altium Designer (AD) 中,Split Planes 功能允许你在一个平面层(例如电源层或地层)上分割出多个不同的区域,每个区域可以分配给不同的网络(net)。这对于设计中需要管理多种电源或接地类型的情况下非常有…...
[linux][命令]linux文件操作命令大全
Linux操作系统提供了丰富的文件操作命令,以下是一些常用的文件操作命令列表: 查看文件内容 cat:查看文件内容。less:分页显示文件内容。more:分页显示文件内容,一次显示一屏。head:查看文件的前…...
大语言模型 (LLM) 窥探未来
初始的探索 在NLP领域,早期的模型如 LSTM 和 GRU 在处理序列数据时取得了一定的成功。但随着数据量和复杂性的增加,这些模型开始显得力不从心。 Transformer的诞生 Transformer 模型的提出,它通过自注意力(Self-Attention&…...
WPF DataGrid调试错误总结
最近WPF中使用了DataGrid做了表格,框架版本为472,遇到了不少的问题,因为软件添加了一个退出进程的全局错误捕获,因此不得不解决所有问题,这边总结一下DataGrid的问题 EditItem is not allowed for this view 按字面意…...
【GCC】结合GPT4 延迟梯度学习1:公式推导及理论分析
大神的分析 本文主要借鉴。【TWCC 】基于gpt和python简化分析webrtc拥塞控制论文: Analysis and Design of the Google Congestion Contro for Web Real-time Communication (WebRTC)感觉应该学习好理论后再进行python 分析:【gcc】基于gpt和python的流程和延迟梯度分析另外:…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
python打卡day49@浙大疏锦行
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...




