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

力扣传送门(opens new window)

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

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

示例 1：

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

示例 2：

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

解题思路：

二叉搜索树（BST）是一种具有以下特性的二叉树：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

要解决这个问题，我们可以利用二叉搜索树的性质以及中序遍历的特点。

中序遍历是指遍历二叉树时，先遍历左子树，然后访问根节点，最后遍历右子树。对于二叉搜索树而言，中序遍历得到的结果是递增有序的。

具体的思路如下：

1. 定义一个全局变量 minDiff，用于保存最小绝对差的值，初始值设为正无穷大。
2. 定义一个全局变量 prev，用于保存中序遍历过程中的前一个节点的值，初始值设为负无穷大。
3. 进行中序遍历：
   • 如果当前节点不为空：
     • 遍历当前节点的左子树，即递归调用函数本身，传入当前节点的左子节点。
     • 计算当前节点值与 prev 的差的绝对值，如果小于 minDiff，则更新 minDiff 的值。
     • 更新 prev 的值为当前节点的值。
     • 遍历当前节点的右子树，即递归调用函数本身，传入当前节点的右子节点。
4. 返回 minDiff，即为最小绝对差的值。

代码实现：

class Solution {
    // 初始化最小绝对差为整数最大值
    int res = Integer.MAX_VALUE;  
    // 用于记录前一个遍历到的节点
    TreeNode prev;  

    public int getMinimumDifference(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        dfs(root.left);

        if (prev != null) {
            res = Math.min(res, Math.abs(root.val - prev.val));
        }
        prev = root;

        dfs(root.right);
    }
}