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

题目描述：

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点的数目范围是 [2, 104]
• 0 <= Node.val <= 105

注意： 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 🔗 相同

---

解题分析及思路：

方法：深度优先搜索

思路： 二叉搜索树（BST）的核心特性是：中序遍历的结果为递增有序序列。

基于这一特性，任意两个节点的最小差值必然出现在中序遍历的相邻节点之间（因为有序序列中，相邻元素的差值最小）。

因此，解题步骤可归纳为：

• 对二叉搜索树进行中序遍历，获取递增序列；
• 遍历过程中记录前一个节点的值，计算当前节点与前一节点的差值；
• 动态更新最小差值，最终得到结果。

func getMinimumDifference(root *TreeNode) int {
	ans := math.MaxInt32
	var prev *TreeNode
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Left)
		if prev != nil && node.Val-prev.Val < ans {
			ans = node.Val - prev.Val
		}
		prev = node
		dfs(node.Right)
	}
	dfs(root)
	return ans
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:8.5 MB,击败了35.82% 的Go用户