530. Minimum Absolute Difference in BST-蒲公英云

530. Minimum Absolute Difference in BST

原题链接： https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/

一个常见的想法是使用中序遍历来遍历这颗BST(因为二叉排序树中序遍历就是一个已经有序的数组)，然后计算相邻两个数的差值，就可以计算得出最小的绝对值之差。

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

如果所给的树不是二叉排序树，那这个时候我们可以借助TreeSet，并且使用先序遍历来帮助我们去寻找最邻近的数对。

public class Solution {
    TreeSet<Integer> set = new TreeSet<>();
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        if (!set.isEmpty()) {
            if (set.floor(root.val) != null) {
                min = Math.min(min, root.val - set.floor(root.val));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, set.ceiling(root.val) - root.val);
            }
        }
        set.add(root.val);
        getMinimumDifference(root.left);
        getMinimumDifference(root.right);
        return min;
    }
}