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

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

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

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

• 示例 1：

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

• 示例 2：

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

• 提示：

树中节点的数目范围是 [2, 10^4]
0 <= Node.val <= 10^5

思路

要找到二叉搜索树中任意两不同节点值之间的最小差值，可以利用二叉搜索树的性质：中序遍历会得到一个递增的有序序列。在这个有序序列中，任意两个不同节点的最小差值必然出现在相邻的两个节点之间。

1. 中序遍历：对二叉搜索树进行中序遍历，将节点值依次存入列表中。在中序遍历过程中，我们可以比较相邻节点的值，找出最小差值。
2. 计算差值：在中序遍历时，比较当前节点和前一个节点的值，计算它们的差值，并更新最小差值。
3. 返回结果：遍历完所有节点后，得到的就是树中任意两不同节点值之间的最小差值。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

class Solution {
    private Integer prev;
    private int minimumDiff = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        // 执行中序遍历
        inorderTraversal(root);
        return this.minimumDiff;
    }

    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        if (this.prev != null) {
            // 更新最小差值
            this.minimumDiff = Math.min(node.val - this.prev, this.minimumDiff);
        }
        this.prev = node.val;
        inorderTraversal(node.right);
    }
}