LeetCode530-Minimum Absolute Difference in BST

题目

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

分析

本题给出的树不是一棵一般的树,而是二叉搜索树(又叫二叉排序树),它有三个重要性质:

  • 左子树上所有节点的值 < 父节点的值
  • 右子树上所有节点的值 > 父节点的值
  • 中序遍历二叉树可得到有序序列

其实照理说性质3应该是性质1、2合起来的推论,有了它我们的思路就很明显啦:既然要求的是树中任两节点相差值的最小值,如果我们能设法把这个数中节点按升序排个序,那所有相邻的两两节点差值中最小的那个一定就是所求。那么正好!中序遍历下来就可以得到有序序列。

到这里我们就要思考如何优化地去实现的问题了。我们不需要鲁莽地用List去存储得到的有序序列然后依次相减。最好的方式是边在遍历的时候,边就计算到了差值。那么很显然,我们需要增加一个min变量记录当前找到的最小差值,用frontVal记录上一个节点的值。但需注意边界条件,就是最初第一个节点,它前面一个节点都还没有,那么frontVal要设置一个最小值(因为它是减数,得到的差值是最大值,比较的是差值),但需要特别注意,这个最小值不能等于Integer.MIN_VALUE,否则在做root.val – frontVal运算的时候必然会超过int的范围。本文设置的是-9999。

代码

public class Solution {
    
    int frontVal = -9999;
    int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null)
            return -1;
        
        //遍历左子树
        getMinimumDifference(root.left);
        
        //访问根
        int gap = root.val - frontVal; //注意这里frontVal最初不能是MIN_VALUE
        min = gap < min ? gap : min;
        frontVal = root.val; //更新作为下一次的比较对象
        
        //遍历右子树
        getMinimumDifference(root.right);
        
        return min;
    }
}

Leave a Comment.