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点取所有结果最小值即是答案。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏