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 i1则中间元素 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.TreeNodeleetcode包没有重复定义树节点而是通过类型别名type alias复用 structures/TreeNode.go 中的公共结构type TreeNode struct { Val int Left *TreeNode Right *TreeNode }这是 LeetCode-Go 仓库的一贯风格把链表、树、堆、区间等常用数据结构统一收敛到structures包中各题解包只写算法逻辑代码更干净、更易对比。2. 哨兵初值的选择res, nodes : math.MaxInt16, -1res初始化为math.MaxInt1632767。由于节点值非负任意两节点的绝对差必然小于该初值保证第一次比较就能正确覆盖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(H)递归调用栈深度取决于树高 H。对平衡 BSTH O(log N)对退化为链的 BSTH O(N)若改为「中序遍历收集有序切片再两两比较相邻差」时间复杂度同样是 O(N)但会额外付出 O(N) 的切片存储空间本解法则把空间占用压缩到只与递归深度相关是空间上更优的写法。测试用例与验证方式测试文件结构仓库为本题提供了完整的测试文件 530. Minimum Absolute Difference in BST_test.go覆盖 4 组用例输入层序遍历数组期望输出覆盖点[4, 2, 6, 1, 3]1常规 BST1 与 2 差 12 与 4 差 23 与 4 差 1[1, 0, 48, null, null, 12, 49]1左右子树跨度大答案出现在右子树内部48 与 49[90, 69, null, 49, 89, null, 52]1深层嵌套的右斜结构52 与 49、89 与 90 均为 1[1, 1]0重复节点两节点值相同差为 0是边界最小值其中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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本注释中说明Go 1.10 支持对多个包一次性传入-coverprofile可直接产出单个合法 profile 文件这是仓库 100% 测试覆盖率策略的基础仓库根目录的 coverage.txt 即由此生成。需要强调的是树形结构属于“结构型”输入对 BST 来说必须保证输入本身满足 BST 约束——上述测试数据全部满足而如[1, 1]这种含重复值的用例在本题定义下依然是一棵合法的 BST允许相等值。与 783 题的对照原题 Note 中明确指出530 与 783Minimum Distance Between BST Nodes是同一道题区别仅在于530 题面强调「任意两个节点的绝对差」并额外给出「节点值为非负」的约束783 题面表述为「任意两个节点的最小距离」取值范围约束略宽。正因如此两份题解的解法骨架完全一致都是「中序遍历 相邻差值取 min」。仓库中这两题各自维护独立的源码与测试文件但核心 DFS 逻辑相同学习时可以直接相互印证。总结Minimum Absolute Difference in BST是“借助数据结构内在有序性完成问题归约”的典型题目识别 BST 特性中序遍历序列天然有序问题归约有序序列中最小绝对差必出现在相邻元素之间从而把「任意两节点」的 O(N²) 枚举降为「相邻两节点」的 O(N) 比较空间优化不必收集完整有序序列遍历过程中滚动维护前驱节点值即可空间复杂度降为 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
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 i1则中间元素 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.TreeNodeleetcode包没有重复定义树节点而是通过类型别名type alias复用 structures/TreeNode.go 中的公共结构type TreeNode struct { Val int Left *TreeNode Right *TreeNode }这是 LeetCode-Go 仓库的一贯风格把链表、树、堆、区间等常用数据结构统一收敛到structures包中各题解包只写算法逻辑代码更干净、更易对比。2. 哨兵初值的选择res, nodes : math.MaxInt16, -1res初始化为math.MaxInt1632767。由于节点值非负任意两节点的绝对差必然小于该初值保证第一次比较就能正确覆盖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(H)递归调用栈深度取决于树高 H。对平衡 BSTH O(log N)对退化为链的 BSTH O(N)若改为「中序遍历收集有序切片再两两比较相邻差」时间复杂度同样是 O(N)但会额外付出 O(N) 的切片存储空间本解法则把空间占用压缩到只与递归深度相关是空间上更优的写法。测试用例与验证方式测试文件结构仓库为本题提供了完整的测试文件 530. Minimum Absolute Difference in BST_test.go覆盖 4 组用例输入层序遍历数组期望输出覆盖点[4, 2, 6, 1, 3]1常规 BST1 与 2 差 12 与 4 差 23 与 4 差 1[1, 0, 48, null, null, 12, 49]1左右子树跨度大答案出现在右子树内部48 与 49[90, 69, null, 49, 89, null, 52]1深层嵌套的右斜结构52 与 49、89 与 90 均为 1[1, 1]0重复节点两节点值相同差为 0是边界最小值其中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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本注释中说明Go 1.10 支持对多个包一次性传入-coverprofile可直接产出单个合法 profile 文件这是仓库 100% 测试覆盖率策略的基础仓库根目录的 coverage.txt 即由此生成。需要强调的是树形结构属于“结构型”输入对 BST 来说必须保证输入本身满足 BST 约束——上述测试数据全部满足而如[1, 1]这种含重复值的用例在本题定义下依然是一棵合法的 BST允许相等值。与 783 题的对照原题 Note 中明确指出530 与 783Minimum Distance Between BST Nodes是同一道题区别仅在于530 题面强调「任意两个节点的绝对差」并额外给出「节点值为非负」的约束783 题面表述为「任意两个节点的最小距离」取值范围约束略宽。正因如此两份题解的解法骨架完全一致都是「中序遍历 相邻差值取 min」。仓库中这两题各自维护独立的源码与测试文件但核心 DFS 逻辑相同学习时可以直接相互印证。总结Minimum Absolute Difference in BST是“借助数据结构内在有序性完成问题归约”的典型题目识别 BST 特性中序遍历序列天然有序问题归约有序序列中最小绝对差必出现在相邻元素之间从而把「任意两节点」的 O(N²) 枚举降为「相邻两节点」的 O(N) 比较空间优化不必收集完整有序序列遍历过程中滚动维护前驱节点值即可空间复杂度降为 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
