530. 二叉搜索树的最小绝对差

题目：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/

代码：

class Solution {

    public int getMinimumDifference(TreeNode root) {
        //左右子树均不存在
        if (root.left == null && root.right == null) {
            return Integer.MAX_VALUE;
        }
        //左子树存在，右子树不存在
        if (root.left != null && root.right == null) {
            return Math.min(root.val - getMax(root.left),this.getMinimumDifference(root.left));
        }
        //左子树不存在，右子树存在
        if (root.left == null && root.right != null) {
            return Math.min(getMin(root.right) - root.val, this.getMinimumDifference(root.right));
        }
        //左右子树均存在
        return Math.min(
                Math.min(root.val - getMax(root.left), getMin(root.right) - root.val),
                Math.min(this.getMinimumDifference(root.left), this.getMinimumDifference(root.right))
        );
    }

    /**
     * 获取root树的最小值
     * @param root
     * @return
     */
    private int getMin(TreeNode root) {
        TreeNode node = root;
        while (node.left != null) {
            node = node.left;
        }
        return node.val;
    }

    /**
     * 获取root树的最大值
     * @param root
     * @return
     */
    private int getMax(TreeNode root) {
        TreeNode node = root;
        while (node.right != null) {
            node = node.right;
        }
        return node.val;
    }

}

因为给定的树是二叉搜索树，所以他的节点是有顺序的，左<右。

我们先定义2个函数getMin和getMax用于获取树root的最大节点和最小节点的值（实现方法很简单直接看代码）。

1、对于树的左边来说，最小绝对差为：root.val-左子树的最大值。

2、对于树的右边来说，最小绝对差为：右子树的最小值-root.val。

3、递归考虑子树中的最小绝对差，考虑左右子树为null值问题（防止空指针异常）。

4、综上3点取所有结果最小值即是答案。