( “树” 之 BST) 530. 二叉搜索树的最小绝对差 ——【Leetcode每日一题】

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。
二叉查找树中序遍历有序。

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

难度：简单

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点的数目范围是 [ 2 , 1 0 4 ] [2, 10^4] [2,104]
• 0 < = N o d e . v a l < = 1 0 5 0 <= Node.val <= 10^5 0<=Node.val<=105

注意： 本题与 783 783. 二叉搜索树节点最小距离 相同

💡思路：

利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值。

🍁代码：(Java、C++)

Java

class Solution {private int minDiff = Integer.MAX_VALUE;private TreeNode preNode = null;public int getMinimumDifference(TreeNode root) {inOrder(root);return minDiff;}private void inOrder(TreeNode node) {if (node == null) return;inOrder(node.left);if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);preNode = node;inOrder(node.right);}
}

C++

class Solution {
public:int minDiff = INT_MAX;TreeNode* pre = nullptr;int getMinimumDifference(TreeNode* root) {inOrder(root);return minDiff;}void inOrder(TreeNode* root){if(root == nullptr) return;inOrder(root->left);if(pre != nullptr) minDiff = min(minDiff, root->val - pre->val);pre = root;inOrder(root->right);}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 $O(n)$ 级别。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！