leetcode日记— 530. Minimum Absolute Difference in BST

发布于 2020-10-12  108 次阅读


题目如下:

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).

思路:

我一开始看错题目了,以为是bst父节点和子节点的最小绝对差,搞了半天还在想为啥会不对。

但是即使是easy的原题目,我也没想出来怎么写。

这道题要先从数学上考虑,在一个递增数列中,所有数字的最小绝对差就一定是相邻两数的差(中最小的)。

那么再结合二叉搜索树的性质,什么时候我们可以遍历出一个递增的序列呢?答案已经很明显了,那就是中序遍历。

好了分析完了,这里注意一个细节—我们需要的是前后差,因此我们应该维护一个全局变量pre,保存上一个节点的值,不需要再使用数组保存前面的结果。

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pre;
    public int res;
    public int getMinimumDifference(TreeNode root) {
        res = Integer.MAX_VALUE;
        pre = -1;
        helper(root);
        return res;
    }
    public void helper(TreeNode root){
        if(root==null)
            return ;
        helper(root.left);
        if(pre==-1)
            pre=root.val;
        else{
            res = Math.min(res,root.val-pre);
            pre = root.val;
        }
        helper(root.right);
        return;
    }
}


你好哇!欢迎来到雷公马碎碎念的地方:)