★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差

★【二叉搜索树】【中序遍历+前后指针】Leetcode 530. 二叉搜索树的最小绝对差

    • 解法1 笨方法 中序遍历转化为有序数组之后遍历
    • 解法2 记忆一下!!!需要用一个pre节点记录一下cur节点的前一个节点

遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。
同时要学会在递归遍历的过程中如何记录前后两个指针

---------------🎈🎈题目链接🎈🎈-------------------
在这里插入图片描述

解法1 笨方法 中序遍历转化为有序数组之后遍历

最大值:Integer.MAX_VALUE
得到ArrayList中的值:arr.get(i)
得到ArrayList的大小:arr.size()

时间复杂度O(N)
空间复杂度O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int getMinimumDifference(TreeNode root) {
        // 中序遍历转化为有序数组之后遍历
        List<Integer> arr = new ArrayList<>();
        helper(root,arr);
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.size()-1;i++){
            int temp = Math.abs(arr.get(i+1)-arr.get(i));
            if(temp < min){
                min = temp;
            }
        }
        return min;
    }
    public void helper(TreeNode root, List<Integer> arr){
        if(root==null) return;

        helper(root.left, arr);
        arr.add(root.val);
        helper(root.right, arr);

    }
}
    

解法2 记忆一下!!!需要用一个pre节点记录一下cur节点的前一个节点

以上代码是把二叉搜索树转化为有序数组了,其实在二叉搜素树中序遍历的过程中,我们就可以直接计算了。
需要用一个pre节点记录一下cur节点的前一个节点
在这里插入图片描述

时间复杂度O(N)
空间复杂度O(N)

可以背一下背一下


 // 采用一个pre节点记录一下cur节点的前一个节点 + 中序遍历【模板题】
class Solution {
    int result = Integer.MAX_VALUE;
    TreeNode pre = null;
    
    public int getMinimumDifference(TreeNode root) {
        helper(root);
        return result;
    }

    public void helper(TreeNode root){
        if(root==null) return;

        helper(root.left);// 左
        if(pre!=null){
            result = Math.min(result,Math.abs(root.val-pre.val));
        }
        pre = root;
        helper(root.right);// 右
    }
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/419260.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一篇教会你升级GPT-4,内附详细步骤(24年3月最新)

先介绍一下 GPT 升级 第一种: 支付宝购买礼品卡给美区 Apple ID 充值 第二种&#xff1a;3分钟快速升级方法&#xff08;一键升级&#xff09; GPT4的作用非常强大&#xff0c;还可以使用DALL进行绘画&#xff0c;比如我画一个小王子的插画&#xff1a; 平时用DALL绘画是比较…

事物

概述&#xff1a; 数据库的事务&#xff08;Transaction&#xff09;是一种机制、一个操作序列&#xff0c;包含了一组数据库操作命令。 事务把所有的命令作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这一组数据库命令要么同时成功&#xff0c;要么同时失败。 事…

SpringCloud搭建微服务之Consul服务配置

1. 概述 前面有介绍过Consul既可以用于服务注册和发现&#xff0c;也可以用于服务配置&#xff0c;本文主要介绍如何使用Consul实现微服务的配置中心&#xff0c;有需要了解如何安装Consul的小伙伴&#xff0c;请查阅SpringCloud搭建微服务之Consul服务注册与发现 &#xff0c…

Ubuntu系统使用Docker搭建Jupyter Notebook并实现无公网ip远程连接

文章目录 1. 选择与拉取镜像2. 创建容器3. 访问Jupyter工作台4. 远程访问Jupyter工作台4.1 内网穿透工具安装4.2 创建远程连接公网地址4.3 使用固定二级子域名地址远程访问 本文主要介绍如何在Ubuntu系统中使用Docker本地部署Jupyter Notebook&#xff0c;并结合cpolar内网穿透…

用GGUF和Llama.cpp量化Llama模型

用GGUF和Llama .cpp量化Llama模型 什么是GGML如何用GGML量化llm使用GGML进行量化NF4 vs. GGML vs. GPTQ结论 由于大型语言模型&#xff08;LLMS&#xff09;的庞大规模&#xff0c;量化已成为有效运行它们的必要技术。通过降低其权重的精度&#xff0c;您可以节省内存并加快推理…

JavaScript数据类型 检测数据类型 数据类型转换 数值相等比较

数值相等比较 JavaScript 提供三种不同的值比较运算&#xff1a; ——严格相等&#xff08;三个等号&#xff09; ——宽松相等&#xff08;两个等号&#xff09; 8种数据类型 前七种为基础数据类型。 Object类型为引用数据类型。 数据类型概念以及存储方式 let a {name:…

MySQL:常用的SQL语句

提醒&#xff1a;设定下面的语句是在数据库名为 db_book执行的。 一、创建表 1. 创建t_booktype表 USE db_book; CREATE TABLE t_booktype(id INT AUTO_INCREMENT, bookTypeName VARCHAR(20),bookTypeDesc varchar(200),PRIMARY KEY (id) );2. 创建t_book表 USE db_book; C…

开源BLHELI-S 代码详细解读(五)

我们继续来看calc_next_comm_timing, 每次操作完换相之后&#xff0c;这里都会调用&#xff0c;同时会设置timer3去等advance timing. 总体思想是根据电机运行状态计算前4次换相时间&#xff0c;然后根据前4次换相时间计算15度和7.5度电角度时间&#xff0c;换相之后延时7.5度…

MYSQL C++链接接口编程

使用MYSQL 提供的C接口来访问数据库,官网比较零碎,又不想全部精读一下,百度CSDN都是乱七八糟的,大部分不可用 官网教程地址 https://dev.mysql.com/doc/connector-cpp/1.1/en/connector-cpp-examples-connecting.html 网上之所以乱七八糟,主要是MYSQL提供了3个接口两个包,使用…

输入一个字符串,将其中的数字字符移动到非数字字符之后

输入一个字符串&#xff0c;将其中的数字字符移动到非数字字符之后&#xff0c;并保持数字字符贺非数字字符输入时的顺序。 代码&#xff1a; #include <cstdio> #include <queue> using namespace std; int main() {char str[200];fgets(str, 200, stdin);//读入…

【详识JAVA语言】输入输出

输出到控制台 基本语法 System.out.println(msg); // 输出一个字符串, 带换行System.out.print(msg); // 输出一个字符串, 不带换行System.out.printf(format, msg); // 格式化输出 println 输出的内容自带 \n, print 不带 \n printf 的格式化输出方式和 C 语言的 printf 是基…

UE蓝图 编译过程详解

系列文章目录 UE蓝图 Get节点和源码 UE蓝图 Set节点和源码 UE蓝图 Cast节点和源码 UE蓝图 分支(Branch)节点和源码 UE蓝图 入口(FunctionEntry)节点和源码 UE蓝图 返回结果(FunctionResult)节点和源码 UE蓝图 函数调用(CallFunction)节点和源码 UE蓝图 序列(Sequence)节点和源…

BUUUCTF---LSB1

1.题目描述&#xff08;提示lsb&#xff09; 2.下载附件是一张图片 3.在010编辑器中查看没有发现什么信息&#xff0c;再看属性也没有什么有用的信息&#xff0c;根据题目提示lsb想到用Stegsolve这个工具 4.在该工具中打开图片 5.先将红绿蓝三种颜色的通道设置成0&#xff0c;…

如何使用Potplayer远程访问本地群晖NAS搭建的WebDAV中的本地资源

文章目录 本教程解决的问题是&#xff1a;按照本教程方法操作后&#xff0c;达到的效果是&#xff1a;1 使用环境要求&#xff1a;2 配置webdav3 测试局域网使用potplayer访问webdav3 内网穿透&#xff0c;映射至公网4 使用固定地址在potplayer访问webdav ​ 国内流媒体平台的内…

Spring八股 常见面试题

什么是Spring Bean 简单来说&#xff0c;Bean 代指的就是那些被 IoC 容器所管理的对象。我们需要告诉 IoC 容器帮助我们管理哪些对象&#xff0c;这个是通过配置元数据来定义的。配置元数据可以是 XML 文件、注解或者 Java 配置类。 将一个类声明为 Bean 的注解有哪些? Com…

什么是虚拟DOM,有什么作用?有了解过diff算法吗?

虚拟DOM&#xff08;Virtual DOM&#xff09;&#xff1a; 虚拟DOM是一个轻量级的JavaScript对象&#xff0c;它是真实DOM&#xff08;Document Object Model&#xff09;的抽象表示。开发者通过操作这个JavaScript对象来描述视图层的状态&#xff0c;当这个状态发生变化时&…

STL容器之vector类

文章目录 STL容器之vector类1、vector的介绍2、vector的使用2.1、vector的常见构造2.2、vector的iterator的使用2.3、vector空间增长问题2.4、vector的增删查改2.5、vector迭代器失效问题 3.vector的模拟实现 STL容器之vector类 1、vector的介绍 vector是表示可变大小数组的序…

常用网络协议的学习

TCP/IP TCP/IP的定义 TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff0c;传输控制协议/互联网协议&#xff09;是互联网的基本协议&#xff0c;也是国际互联网络的基础。 TCP/IP 不是指一个协议&#xff0c;也不是 TCP 和 IP 这两个协议的合称…

天津廉租房如何申请取得廉租住房租房补贴资格

如何申请廉租住房租赁补贴资格&#xff1f; 低收入住房困难家庭应当向户籍所在地街道办事处&#xff08;乡镇人民政府&#xff09;提出申请。 申请时&#xff0c;您需要提供以下要求的原件和复印件&#xff1a; &#xff08;一&#xff09;您及家人的身份证件&#xff1b; &a…

海外代理IP干货:应该选择SOCKS55代理还是Http代理?

在使用IPFoxy全球代理时&#xff0c;选择 SOCKS55代理还是HTTP代理&#xff1f;IPFoxy代理可以SOCKS55、Http协议自主切换&#xff0c;但要怎么选择&#xff1f;为解决这个问题&#xff0c;得充分了解两种代理的工作原理和配置情况。 在这篇文章中&#xff0c;我们会简要介绍 …