LeetCode_70_MinimumAbsoluteDifferenceInBST

1. question: 二叉搜索树的最小绝对差（简单）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst

示例 1：

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

示例 2：

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

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

2. answers

这道题的思路和验证二叉搜索树是一样的思路。二叉搜索树的最小绝对差只能出现在相邻节点中。此时中序遍历的时候，计算差值，并比较是否是最小值即可。先采用保存中序序列的方法做一下，代码如下所示：

public class Solution_0069 {

    // 中序遍历
    public static void midOrder(TreeNode root, List<Integer> result) {

        if(root == null) return;

        midOrder(root.left, result);

        result.add(root.val);

        midOrder(root.right, result);
    }

    public static int getMinimumDifference(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        midOrder(root, result);

        // 遍历，比较最小值。
        int val = result.get(1) - result.get(0);

        int temp;

        for (int i = 2; i < result.size(); i++) {

            temp = result.get(i) - result.get(i - 1);
            if(temp < val) val = temp;
        }

        return val;
    }

    public static void main(String[] args) {

//        TreeNode tn5 = new TreeNode(3);
//        TreeNode tn4 = new TreeNode(1);
//        TreeNode tn3 = new TreeNode(2, tn4, tn5);
//        TreeNode tn2 = new TreeNode(6);
//        TreeNode tn1 = new TreeNode(4, tn3, tn2);
//
//        System.out.println(getMinimumDifference(tn1));

        TreeNode tn5 = new TreeNode(49);
        TreeNode tn4 = new TreeNode(12);
        TreeNode tn3 = new TreeNode(48, tn4, tn5);
        TreeNode tn2 = new TreeNode(0);
        TreeNode tn1 = new TreeNode(1, tn2, tn3);

        System.out.println(getMinimumDifference(tn1));
    }
}

同样，可以在中序遍历的过程中就比较，无需存储序列。注意，LeetCode似乎不适合用静态变量和静态方法。所以还是按照标准来。

public class Solution_0069_02 {

    // 不知道为啥，这种在LeetCode上的结果和在本机上不一样。
    // 这里设置最小值为最大值，方便差值一定不是最小值
//    public static int pre = Integer.MAX_VALUE;
//    public static int min = Integer.MAX_VALUE;

    public int pre;
    public int min;

    // 中序遍历
    public void midOrder(TreeNode root) {

        if(root == null) return;

        midOrder(root.left);

        // 在第二个节点时开始计算并比较
        if(pre == -1) {
            min = Integer.MAX_VALUE;

        } else {
            if(Math.abs(root.val - pre) < min) min = Math.abs(root.val - pre);
        }

        pre = root.val;

        midOrder(root.right);
    }

    public int getMinimumDifference(TreeNode root) {

        pre = -1;
        min = Integer.MAX_VALUE;

        midOrder(root);

        return min;

    }

    public static void main(String[] args) {

//        TreeNode tn5 = new TreeNode(49);
//        TreeNode tn4 = new TreeNode(12);
//        TreeNode tn3 = new TreeNode(48, tn4, tn5);
//        TreeNode tn2 = new TreeNode(0);
//        TreeNode tn1 = new TreeNode(1, tn2, tn3);
//
//        System.out.println(getMinimumDifference(tn1));

//        TreeNode tn5 = new TreeNode(3);
//        TreeNode tn4 = new TreeNode(1);
//        TreeNode tn3 = new TreeNode(2, tn4, tn5);
//        TreeNode tn2 = new TreeNode(6);
//        TreeNode tn1 = new TreeNode(4, tn3, tn2);
//
//        System.out.println(getMinimumDifference(tn1));

        TreeNode tn3 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(5, tn3, null);
        TreeNode tn1 = new TreeNode(1, null, tn2);

        Solution_0069_02 s = new Solution_0069_02();
//
        System.out.println(s.getMinimumDifference(tn1));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。