26_二叉搜索树的最小绝对差

简介: 26_二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差

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

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

示例 1:

输入:root = [4,2,6,1,3]
输出:1

示例 2:

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

【思路】

题目要求在二叉搜索树上任意两节点的差的绝对值的最小值。

注意是二叉搜索树,二叉搜索树是有序的。遇到在二叉搜索树上求最值、差值之类的,就把它想成在一个有序数组上求最值、差值,这样就简答多了。

class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }
    public void traversal(TreeNode root){
        if(root==null)return;
        //左
        traversal(root.left);
        //中
        if(pre!=null){
            result = Math.min(result,root.val-pre.val);
        }
        pre = root;
        //右
        traversal(root.right);
    }
}
class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        int result = Integer.MAX_VALUE;
        if(root != null)
            stack.add(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if(curr != null){
                stack.pop();
                if(curr.right != null)
                    stack.add(curr.right);
                stack.add(curr);
                stack.add(null);
                if(curr.left != null)
                    stack.add(curr.left);
            }else{
                stack.pop();
                TreeNode temp = stack.pop();
                if(pre != null)
                    result = Math.min(result, temp.val - pre.val);
                pre = temp;
            }
        }
        return result;
    }
}
相关文章
|
网络协议 Linux 数据处理
网络编程【网络编程基本概念、 网络通信协议、IP地址 、 TCP协议和UDP协议】(一)-全面详解(学习总结---从入门到深化)
网络编程【网络编程基本概念、 网络通信协议、IP地址 、 TCP协议和UDP协议】(一)-全面详解(学习总结---从入门到深化)
1227 3
|
消息中间件 存储 监控
ActiveMQ系列: ActiveMQ 的死信队列与消费重试机制
maximumRedeliveryDelay:最大传送延迟,只在 useExponentialBackOff 为 true 时有效(V5.5),假设首次重连间隔为 10ms,倍数为 2,那么第二次重连时间间隔为 20ms,第三次重连时间间隔为 40ms,当重连时间间隔大的最大重连时间间隔时,以后每次重连时间间隔都为最大重连时间间隔。默认为 -1。
1881 0
ActiveMQ系列: ActiveMQ 的死信队列与消费重试机制
|
传感器 数据采集 算法
【免费开源】基于 STM32F4 的四轴飞行器设计与实现——从零开始到成功起飞(项目源码打包分享)
四轴飞行器作为一种低空、低成本的遥感平台,已经在多个领域展现出广泛的应用潜力。相比其他类型的飞行器,它在硬件上结构紧凑、安装方便,但在软件层面却充满挑战——从传感器数据融合到姿态解算,再到快速且稳定的控制算法,每一环节都需要精心设计,也正因此让四轴飞行器更具技术魅力。
1483 74
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
686 0
|
JavaScript 前端开发 API
Node.js中发起HTTP请求的五种方式
以上五种方式,尽管只是冰山一角,但已经足以让编写Node.js HTTP请求的你,在连接世界的舞台上演奏出华丽的乐章。从原生的 `http`到现代的 `fetch`,每种方式都有独特的风格和表现力,让你的代码随着项目的节奏自由地舞动。
1137 65
|
数据采集 人工智能 自然语言处理
FireCrawl:开源 AI 网络爬虫工具,自动爬取网站及子页面内容,预处理为结构化数据
FireCrawl 是一款开源的 AI 网络爬虫工具,专为处理动态网页内容、自动爬取网站及子页面而设计,支持多种数据提取和输出格式。
6962 71
FireCrawl:开源 AI 网络爬虫工具,自动爬取网站及子页面内容,预处理为结构化数据
|
缓存 网络协议 算法
从零开始掌握HTTP协议:全面详解1.0、1.1和2.0
大家好!我是小米,今天带大家深入探讨互联网基础——HTTP协议。从HTTP/1.0到HTTP/1.1,再到HTTP/2.0,它们是如何发展的,解决了哪些问题,有哪些显着区别?通过这这篇文章,你将全面了解这些协议的变革和优化,掌握关键技术点,提升开发效率。快来一起学习吧!
1160 1
|
存储 JSON 监控
微服务链路追踪原理,一文搞懂!
本文重点讲解微服务链路追踪(Microservices Distributed Tracing),介绍其原理、架构及工作流程。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
微服务链路追踪原理,一文搞懂!
|
网络协议 安全 应用服务中间件
服务器最大支持多少链接数
本文探讨了单台服务器最大支持的链接数问题,指出操作系统通过四元组(本地IP、本地端口、远程IP、远程端口)唯一标识TCP链接。链接数不仅受限于端口数量(65535),还与系统文件句柄上限、内存资源及是否绑定多个IP地址有关。通过调整系统配置和利用多IP技术,理论上可大幅提高单机支持的链接数,但实际应用中还需考虑硬件资源限制。
1353 16
|
前端开发 Java 中间件
过滤器(Filter)和拦截器(Interceptor)有什么不同?
文章比较了过滤器(Filter)和拦截器(Interceptor)的不同,包括它们的实现方式、应用场景、执行顺序、依赖框架和访问范围,指出过滤器通常用于全局和非业务相关的操作,而拦截器用于Spring MVC中与业务逻辑相关的处理。
1329 8