leetcode530-二叉搜索树的最小绝对差

原题

给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。

示例:

输入:

   1
    \
     3
    /
  2

输出:
1
解释:
最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。

注意: 树中至少有2个节点。

解法

思想

中序遍历,计算两个相邻节点之间值的差的绝对值,比较出最小值。

代码

class Solution {
    int min = Integer.MAX_VALUE;
    int last = -1;
    public int getMinimumDifference(TreeNode root) {
        traverse(root);
        return min;
    }
    public void traverse(TreeNode root){
        if(root == null){
            return;
        }
        traverse(root.left);
        if(last!=-1) min = Math.min(min,root.val-last);
        last = root.val;
        traverse(root.right);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode530-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e7%9a%84%e6%9c%80%e5%b0%8f%e7%bb%9d%e5%af%b9%e5%b7%ae/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月22日
下一篇 2020年2月22日

相关推荐

  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330
  • 剑指offer64-求1+2+…+n

    原题(来源Leetcode) 求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例1…

    算法 2020年6月2日
    0560
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • 程序员面试金典01.07-旋转矩阵

    原题(来源Leetcode) 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。 不占用额外内存空间能否做到? 示例 …

    算法 2020年4月7日
    0410
  • leetcode1114-按序打印

    原题 我们提供了一个类: public class Foo {   public void one() { print("one"); }   public void two() …

    算法 2020年2月1日
    0140
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    080
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    0100
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    090
  • leetcode779-第K个语法符号

    原题 在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。 给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始) 例子: 输入: N…

    算法 2020年1月22日
    0110
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170

发表回复

登录后才能评论