LeetCode-Go 题解：530. Minimum Absolute Difference in BST —— 利用 BST 中序遍历求任意两节点最小绝对差

LeetCode-Go 题解：530. Minimum Absolute Difference in BST —— 利用 BST 中序遍历求任意两节点最小绝对差

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 leetcode/0530.Minimum-Absolute-Difference-in-BST/README.md 的题解为主线，结合 530. Minimum Absolute Difference in BST.go 源码与_test.go测试用例，深入拆解「中序遍历 + 相邻差值滚动比较」的经典做法，并给出复杂度分析、等价题 783 的对照与本地验证方式。

题目概述

原题要求：给定一棵所有节点值为非负整数的二叉搜索树（BST），找出树中任意两个节点的值的绝对差的最小值。

题目保证树中至少有两个节点（There are at least two nodes in this BST），因此答案恒有意义。

Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

以上面的树为例：节点 1 与 2 的差为 1，节点 2 与 3 的差也为 1，因此最小绝对差为 1。

本题在 LeetCode 上注明与783. Minimum Distance Between BST Nodes完全相同（仅题面表述不同），因此解题代码可直接复用。

核心思路：BST 中序遍历的有序性

二叉搜索树最根本的性质是：对 BST 进行中序遍历（左子树 → 根 → 右子树），得到的节点值序列是严格递增有序的。

于是「任意两节点之差的绝对值最小」问题发生了一次漂亮的归约：

• 在一个已排序序列中，任意两元素差值的绝对值最小值，必然出现在相邻两个元素之间（可反证：若最小值来自非相邻元素 a[i]、a[j]（j > i+1），则中间元素 a[k] 必满足 a[i] ≤ a[k] ≤ a[j]，|a[i]-a[k]| 或 |a[k]-a[j]| 必然不大于 |a[i]-a[j]|，与“最小”矛盾）。
• 因此只需中序遍历 BST，动态维护「上一个被访问的节点值」与「当前节点值」的差值，不断取最小值即可。

该思路在原文档「解题思路」一节中也有直接阐述（见 README.md）：

由于是 BST 树，利用它有序的性质，中根遍历的结果是有序的。中根遍历过程中动态维护前后两个节点的差值，即可找到最小差值。

仓库源码逐行解析

仓库中的核心实现位于 530. Minimum Absolute Difference in BST.go，完整代码如下：

package leetcode import ( "math" "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func getMinimumDifference(root *TreeNode) int { res, nodes := math.MaxInt16, -1 dfsBST(root, &res, &nodes) return res } func dfsBST(root *TreeNode, res, pre *int) { if root == nil { return } dfsBST(root.Left, res, pre) if *pre != -1 { *res = min(*res, abs(root.Val-*pre)) } *pre = root.Val dfsBST(root.Right, res, pre) } func min(a, b int) int { if a > b { return b } return a } func abs(a int) int { if a > 0 { return a } return -a }

关键设计点拆解

1. 复用公共 TreeNode 结构

// TreeNode define type TreeNode = structures.TreeNode

leetcode包没有重复定义树节点，而是通过类型别名（type alias）复用 structures/TreeNode.go 中的公共结构：

type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

这是 LeetCode-Go 仓库的一贯风格：把链表、树、堆、区间等常用数据结构统一收敛到structures包中，各题解包只写算法逻辑，代码更干净、更易对比。

2. 哨兵初值的选择

res, nodes := math.MaxInt16, -1

• res初始化为math.MaxInt16（32767）。由于节点值非负，任意两节点的绝对差必然小于该初值，保证第一次比较就能正确覆盖；
• nodes充当「前驱节点值」哨兵，初始为-1。因为节点值非负，-1与任何真实节点值都不可能冲突，于是if *pre != -1可以可靠地判断「是否已经访问过第一个节点」。

需要注意一个隐含约束：该写法成立的前提是节点值为非负数（题目恰好给出了这个前提）。如果题目允许负值节点，哨兵就需要换用独立的布尔标志位来记录「是否已有前驱」。

3. 中序遍历与滚动更新

dfsBST(root.Left, res, pre) // ① 先遍历左子树 if *pre != -1 { // ② 处理当前节点 *res = min(*res, abs(root.Val-*pre)) } *pre = root.Val // ③ 更新前驱 dfsBST(root.Right, res, pre) // ④ 再遍历右子树

递归访问顺序严格遵循「左-根-右」。每当访问到一个节点时，用abs(root.Val-*pre)计算它与前驱节点的绝对差，再用min与历史最优*res比较并更新。遍历完成后*res即为全局最小绝对差。

注意res、pre均以指针方式传入递归函数，保证整个遍历过程共享同一份状态，避免每次递归拷贝副本。

复杂度分析

若改为「中序遍历收集有序切片，再两两比较相邻差」，时间复杂度同样是 O(N)，但会额外付出 O(N) 的切片存储空间；本解法则把空间占用压缩到只与递归深度相关，是空间上更优的写法。

测试用例与验证方式

测试文件结构

仓库为本题提供了完整的测试文件 530. Minimum Absolute Difference in BST_test.go，覆盖 4 组用例：

其中null在仓库中用常量structures.NULL（-1 << 63，见 structures/TreeNode.go）表示，测试数据里直接写作structures.NULL。

测试数据的构造方式

测试用例以层序遍历数组形式给出，由 structures/TreeNode.go 中的Ints2TreeNode(ints []int)转换为树结构：

func Ints2TreeNode(ints []int) *TreeNode { n := len(ints) if n == 0 { return nil } root := &TreeNode{Val: ints[0]} queue := make([]*TreeNode, 1, n*2) queue[0] = root i := 1 for i < n { node := queue[0] queue = queue[1:] if i < n && ints[i] != NULL { node.Left = &TreeNode{Val: ints[i]} queue = append(queue, node.Left) } i++ if i < n && ints[i] != NULL { node.Right = &TreeNode{Val: ints[i]} queue = append(queue, node.Right) } i++ } return root }

实现采用队列做层序建树：遇到NULL哨兵值就跳过该子节点，否则创建节点并入队。测试主流程Test_Problem530对每组数据执行structures.Ints2TreeNode(p.one)建树，再调用getMinimumDifference(rootOne)断言结果。

在本地运行验证

在仓库根目录执行以下命令，即可运行 530 题的全部测试用例（仅针对该题）：

go test -v -run Test_Problem530 ./leetcode/0530.Minimum-Absolute-Difference-in-BST/

若想生成覆盖率报告，可参考仓库根目录的 gotest.sh 脚本中的方式：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该脚本注释中说明：Go 1.10+ 支持对多个包一次性传入-coverprofile，可直接产出单个合法 profile 文件，这是仓库 100% 测试覆盖率策略的基础（仓库根目录的 coverage.txt 即由此生成）。需要强调的是：树形结构属于“结构型”输入，对 BST 来说必须保证输入本身满足 BST 约束——上述测试数据全部满足，而如[1, 1]这种含重复值的用例，在本题定义下依然是一棵合法的 BST（允许相等值）。

与 783 题的对照

原题 Note 中明确指出：530 与 783（Minimum Distance Between BST Nodes）是同一道题，区别仅在于：

• 530 题面强调「任意两个节点的绝对差」，并额外给出「节点值为非负」的约束；
• 783 题面表述为「任意两个节点的最小距离」，取值范围约束略宽。

正因如此，两份题解的解法骨架完全一致：都是「中序遍历 + 相邻差值取 min」。仓库中这两题各自维护独立的源码与测试文件，但核心 DFS 逻辑相同，学习时可以直接相互印证。

总结

Minimum Absolute Difference in BST是“借助数据结构内在有序性完成问题归约”的典型题目：

1. 识别 BST 特性：中序遍历序列天然有序；
2. 问题归约：有序序列中最小绝对差必出现在相邻元素之间，从而把「任意两节点」的 O(N²) 枚举降为「相邻两节点」的 O(N) 比较；
3. 空间优化：不必收集完整有序序列，遍历过程中滚动维护前驱节点值即可，空间复杂度降为 O(H)。

仓库实现（530. Minimum Absolute Difference in BST.go）以 4 组覆盖常规、跨子树、深层嵌套与重复节点场景的测试用例（530. Minimum Absolute Difference in BST_test.go）验证了正确性。掌握这一模式后，可顺带解决 783 题，并迁移到其他“求 BST 有序序列相邻关系极值”的问题（如 230. Kth Smallest Element in a BST 的计数版中序遍历思路）。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go