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

二叉树——二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

链接
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:
在这里插入图片描述

输入:root = [4,2,6,1,3]
输出:1
示例 2:
在这里插入图片描述

输入:root = [1,0,48,null,null,12,49]
输出:1

提示:

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

递归法

方法一

用中序遍历把二叉搜索树的值存在vector< int >中,成单调递增,计算差值就可以了

方法二

在递归中直接计算

  • 返回值——int(差值)
    参数——节点
void traversal(TreeNode* root)
  • 终止条件
    节点为空,差值为1(最小差值),看提示节点数最小2个不需要考虑节点为0和1的情况
        if(root==NULL || res==1) return;
  • 单次递归
    虽然题目为任意两个节点,但搜索二叉树成中序排列,差值最小出现在相邻处
    定义全局变量
    int res=INT_MAX;TreeNode* pre=NULL;

中序递归

        if(root->left)traversal(root->left);//左if(root!=NULL&& pre!=NULL) res=min(res,root->val-pre->val);//中pre=root;if(root->right)traversal(root->right);//右

中的操作有两步

  1. 计算差值,取最小值
  2. 记录上一个节点

代码

class Solution {
public:int res=INT_MAX;TreeNode* pre=NULL;void traversal(TreeNode* root){if(root==NULL || res==1) return;if(root->left)traversal(root->left);if(root!=NULL&& pre!=NULL) res=min(res,root->val-pre->val);pre=root;if(root->right)traversal(root->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return res;}
};

相关文章:

二叉树——二叉搜索树的最小绝对差

二叉搜索树的最小绝对差 链接 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数&#xff0c;其数值等于两值之差的绝对值。 示例 1&#xff1a; 输入&#xff1a;root [4,2,6,1,3] 输出&#xff1a;1 示例 2&…...

git的使用(终端输入指令)下

文章目录前言1、git 分支创建分支查看分支切换分支合并分支删除分支2.提交到远程仓库远程提交链接一下自己仓库总结前言 上章链接 &#xff1a;git的使用&#xff08;终端输入指令&#xff09;上 我们接着上着来说 上章把 git 的 功能实现了一部分&#xff0c;本章我们接着上文…...

python使用influxdb-client管理InfluxDB的bucket

bucket的概念类似数据库的“库”&#xff0c;同时每个库中的数据都因为存在“时间戳”&#xff0c;每个数据都会有一个对应的时间点 influxdb-client-python官方github页面&#xff1a;https://github.com/influxdata/influxdb-client-python 管理bucket的官方示例&#xff1…...

【c++】模板2—类模板

文章目录类模板语法类模板与函数模板区别类模板中成员函数常见时机类模板对象做函数参数类模板与继承类模板成员函数类外实现类模板分文件编写类模板与友元类模板语法 类模板作用&#xff1a; 建立一个通用类&#xff0c;类中的成员数据类型可以不具体制定&#xff0c;用一个虚…...

基于SpringCloud的可靠消息最终一致性03:项目骨架代码(下)

上一节把整个项目的演示内容、项目结构、POM文件和配置文件都讲完了,接下来继续。 先安装并启动Nacos,然后在其中建立一个名为xiangwang-payment-dev.yaml的配置文件,内容为: # 指定运行环境 spring:autoconfigure:exclude: com.alibaba.druid.spring.boot.autoconfigure.D…...

linux如何彻底的删除文件

一、使用rm命令删除 直接用rm 先用ls -alt看下文件信息及拥有者等 可以看到拥有者是eve用户&#xff0c;所以在eve用户的终端中rm命令即可&#xff0c; 如果是root或者其他&#xff0c;则优先用root或其他账号进行删除 (base) eveEve:~$ ls -alt a.txt -rw-rw-r-- 1 eve eve …...

数据仓库Hive的安装和部署

1&#xff09;去apache.hive.org官网下载hive 目前hive主要有三大版本&#xff0c;Hive1.x、Hive2.x、Hive3.x Hive1.x已经2年没有更新了&#xff0c;所以这个版本后续基本不会再维护了&#xff0c;不过这个版本已经迭代了很多年了&#xff0c;也是比较稳定的 Hive2.x最近一直…...

Python调用CANoe常见问题

一、Win32com已经安装成功但是在pycharm中提示错误 No module named win32com.clientPyCharm中出现unresolved reference的解决方法 一直提示需要升级pip版本Pywin32已成功安装,但仍提示没有win32com模块...

一起Talk Android吧(第五百零七回:图片滤镜ImageFilterView)

文章目录背景介绍功能介绍图片滤镜图片圆角图片缩放图片旋转图片平移各位看官们大家好&#xff0c;上一回中咱们说的例子是"如何调整组件在约束布局中的角度",这一回中咱们说的例子是" 图片滤镜ImageFilterView"。闲话休提&#xff0c;言归正转&#xff0c…...

Java 解释器和即时解释器(JIT)之间的区别

区别是&#xff1a; 翻译 .class &#xff08;字节码文件&#xff09; 的粒度和方式不同 解释器是一个逐条解释并执行字节码指令的组件&#xff0c;每次**只翻译一条**指令并执行&#xff0c;然后再翻译下一条指令。 它的翻译粒度是一条指令&#xff0c;而且是按需翻译&#x…...

Acwing 蓝桥杯 第二章 二分与前缀和

今天来补一下之前没写的总结&#xff0c;题是写完了&#xff0c;但是总结没写感觉没什么好总结的啊&#xff0c;就当打卡了789. 数的范围 - AcWing题库思路&#xff1a;一眼二分&#xff0c;典中典先排个序&#xff0c;再用lower_bound和upper_bound维护相同的数的左界和右界就…...

CSDN原力增长规则解读 实测一个月

CSDN原力越来越难了&#xff0c;当然&#xff0c;这对生态发展来说也是好事。介绍下原力增长有哪些渠道吧。发布原创文章&#xff1a;10分/次&#xff0c;每日上限为15分、2篇回答问题&#xff1a;1分/次&#xff0c;每日上限2分&#xff0c;2回答发动态&#xff1a;1分/次&…...

HDMI协议介绍(三)--InfoFrame

目录 Auxiliary Video information (AVI) InfoFrame AVI InfoFrame包结构 Header Body 举个例子 附录 Audio InfoFrame Audio InfoFrame包结构 Header Body Vendor Specific InfoFrame Vendor Specific InfoFrame包结构 Header Body AVI/AUDIO/VSI Infoframe都…...

【RocketMQ】源码详解:Broker端消息储存流程、消息格式

消息存储流程 入口&#xff1a; org.apache.rocketmq.remoting.netty.NettyRemotingAbstract#processRequestCommand org.apache.rocketmq.broker.processor.SendMessageProcessor#asyncProcessRequest 消息到达broker后会经过netty的解码、消息处理器等&#xff0c;最后根据…...

IoT项目系统架构案例2

项目背景 1.这个项目是对之前的案例的升级改造参考&#xff1a;IoT项目系统架构案例_iot案例_wxgnolux的博客-CSDN博客2.基于方案1的项目实施过程中碰到的问题,对硬件设备标准化的理念及新的功能需求(如根据天气预报温度调水温,APP界面可操作性优化等)•采用目前IoT主流厂商的架…...

Vue echarts封装

做大屏的时候经常会遇到 echarts 展示&#xff0c;下面展示在 Vue2.7 / Vue3 中对 echarts &#xff08;^5.4.0&#xff09; 的简单封装。 文章首发于https://blog.fxss.work/vue/echarts封装.html&#xff0c;样例查看 echarts 封装使用 props 说明 参数说明类型可选值默认…...

蓝桥杯入门即劝退(二十二)反转字符(不走寻常路)

欢迎关注点赞评论&#xff0c;共同学习&#xff0c;共同进步&#xff01; ------持续更新蓝桥杯入门系列算法实例-------- 如果你也喜欢Java和算法&#xff0c;欢迎订阅专栏共同学习交流&#xff01; 你的点赞、关注、评论、是我创作的动力&#xff01; -------希望我的文章…...

数据仓库Hive

HIve介绍 Hive是建立在Hadoop上的数据仓库基础构架。它提供了一系列的工具&#xff0c;可以用来进行数据提取转化加载&#xff0c;可以简称为ETL。 Hive 定义了简单的类SQL查询语言&#xff0c;称为HQL&#xff0c;它允许熟悉SQL的用户直接查询Hadoop中的数据&#xf…...

嵌入式 STM32 步进电机驱动,干货满满,建议收藏

目录 步进电机 1、步进电机驱动原理 2、步进电机驱动 3、步进电机应用 1、第一步&#xff1a;初始化IO口 2、设置行进方式 四、源码 步进电机 步进电机被广泛应用于ATM机、喷绘机、刻字机、写真机、喷涂设备、医疗仪器及设备、计算机外设及海量存储设备、精密仪器、工业…...

详讲函数.2.

目录 5. 函数的嵌套调用和链式访问 5.1 嵌套调用 5.2 链式访问 小结&#xff1a; 6. 函数的声明和定义 6.1 函数的声明&#xff1a; 6.2 函数的定义&#xff1a; 5. 函数的嵌套调用和链式访问 函数和函数之间可以根据实际的需求进行组合的&#xff0c;也就是互相调用的…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...