登录
LeetCode 530. 二叉搜索树的最小绝对差：两种解法详解（迭代+递归）
LeetCode 上一道经典的二叉搜索树（BST）题目——530. 二叉搜索树的最小绝对差，这道题看似简单，却能很好地考察我们对 BST 特性的理解，以及二叉树遍历方式的灵活运用。下面我会从题目分析、核心思路、两种解法拆解，到代码细节注释，一步步帮大家搞懂这道题，新手也能轻松跟上。
一、题目解读
题目很直白：给一个二叉搜索树的根节点 root，返回树中任意两个不同节点值之间的最小差值，差值是正数（即两值之差的绝对值）。
这里有个关键前提——二叉搜索树的特性：中序遍历二叉搜索树，得到的序列是严格递增的（假设树中没有重复值，题目未明确说明，但测试用例均满足此条件）。
这个特性是解题的核心！因为递增序列中，任意两个元素的最小差值，一定出现在相邻的两个元素之间。比如序列 [1,3,6,8]，最小差值是 3-1=2，而不是 8-1=7 或 6-3=3。所以我们不需要暴力枚举所有两两组合，只需要在中序遍历的过程中，记录前一个节点的值，与当前节点值计算差值，不断更新最小差值即可。
二、核心解题思路
-
利用 BST 中序遍历为递增序列的特性，将“任意两节点的最小差值”转化为“中序序列中相邻节点的最小差值”；
-
遍历过程中，维护两个变量：
min（记录当前最小差值，初始值设为无穷大）、pre（记录前一个节点的值，初始值设为负无穷大，避免初始值影响第一次差值计算）； -
遍历每个节点时，用当前节点值与
pre计算绝对值差值，更新min，再将pre更新为当前节点值； -
遍历结束后，
min即为答案。
接下来，我们用两种最常用的遍历方式实现这个思路：迭代中序遍历（解法1）和递归中序遍历（解法2）。
三、解法一：迭代中序遍历（非递归）
迭代遍历的核心是用“栈”模拟递归的调用过程，避免递归深度过深导致的栈溢出（虽然这道题的测试用例大概率不会出现，但迭代写法更通用，适合处理大型树）。
3.1 代码实现（带详细注释）
// 先定义 TreeNode 类（题目已给出，此处复用）
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
}
}
// 解法1：迭代中序遍历
function getMinimumDifference_1(root: TreeNode | null): number {
// 边界处理：空树返回0（题目中树至少有一个节点？但严谨起见还是判断）
if (!root) return 0;
let min = Infinity; // 最小差值，初始为无穷大
let pre = -Infinity; // 前一个节点的值，初始为负无穷大
const stack: TreeNode[] = []; // 用于模拟中序遍历的栈
let curr: TreeNode | null = root; // 当前遍历的节点
// 第一步：将左子树所有节点压入栈（中序遍历：左 -> 根 -> 右）
while (curr) {
stack.push(curr);
curr = curr.left; // 一直向左走，直到最左节点
}
// 第二步：弹出栈顶节点，处理根节点，再遍历右子树
while (stack.length) {
const node = stack.pop(); // 弹出栈顶（当前要处理的根节点）
if (!node) continue; // 防止空节点（理论上不会出现）
// 处理右子树：将右子树的所有左节点压入栈
if (node.right) {
let right: TreeNode | null = node.right;
while (right) {
stack.push(right);
right = right.left;
}
}
// 计算当前节点与前一个节点的差值，更新最小差值
min = Math.min(min, Math.abs(pre - node.val));
// 更新pre为当前节点值，为下一个节点做准备
pre = node.val;
}
return min;
};
3.2 思路拆解
-
初始化：栈用于存储待处理的节点，curr指向根节点，先将根节点的所有左子节点压入栈（因为中序遍历要先访问左子树）；
-
弹出栈顶节点（此时该节点的左子树已处理完毕），先处理其右子树（将右子树的所有左节点压入栈，保证下一次弹出的是右子树的最左节点）；
-
计算当前节点与pre的差值，更新min，再将pre更新为当前节点值；
-
重复上述过程，直到栈为空，遍历结束。
优势：不依赖递归栈，避免递归深度过大导致的栈溢出，空间复杂度由递归的 O(h)（h为树高）优化为 O(h)（栈的最大深度也是树高），实际运行更稳定。
四、解法二：递归中序遍历
递归写法更简洁，代码量少，思路也更直观，适合树的深度不大的场景。核心是用递归函数实现中序遍历的“左 -> 根 -> 右”顺序。
4.1 代码实现（带详细注释）
// 解法2：递归中序遍历
function getMinimumDifference_2(root: TreeNode | null): number {
if (!root) return 0;
let min = Infinity; // 最小差值
let pre = -Infinity; // 前一个节点的值
// 递归函数：实现中序遍历
const dfs = (node: TreeNode) => {
if (!node) return; // 递归终止条件：节点为空
// 1. 遍历左子树（左）
if (node.left) dfs(node.left);
// 2. 处理当前节点（根）：计算差值，更新min和pre
min = Math.min(min, Math.abs(pre - node.val));
pre = node.val;
// 3. 遍历右子树（右）
if (node.right) dfs(node.right);
}
// 从根节点开始递归
dfs(root);
return min;
};
4.2 思路拆解
-
定义递归函数 dfs，参数为当前节点，负责遍历以该节点为根的子树；
-
递归终止条件：当前节点为空，直接返回；
-
先递归遍历左子树（保证左子树先被处理）；
-
处理当前节点：计算当前节点与pre的差值，更新min，再将pre更新为当前节点值；
-
最后递归遍历右子树；
-
从根节点调用dfs，完成整个树的遍历，返回min。
优势：代码简洁，思路直观，容易理解和编写；劣势：当树的深度很大时（如链式树），会出现递归栈溢出，此时迭代写法更合适。
五、两种解法对比与总结
| 解法 | 遍历方式 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 |
|---|---|---|---|---|---|
| 解法1 | 迭代中序 | O(n)（每个节点遍历一次） | O(h)（h为树高，栈的最大深度） | 稳定，无栈溢出风险，通用 | 代码稍长，需要手动维护栈 |
| 解法2 | 递归中序 | O(n)（每个节点遍历一次） | O(h)（递归栈深度） | 代码简洁，思路直观，易编写 | 深度过大时会栈溢出 |
关键总结
-
这道题的核心是利用 BST 中序遍历为递增序列，将“任意两节点最小差值”转化为“相邻节点最小差值”，避免暴力枚举；
-
两种解法的核心逻辑一致，只是遍历方式不同，可根据树的深度选择：树深较小时用递归，树深较大时用迭代；
-
注意初始值的设置：min设为无穷大（保证第一次差值能更新min），pre设为负无穷大（避免初始值与第一个节点值计算出不合理的差值）；
-
边界处理：空树返回0（题目中树至少有一个节点，但严谨起见必须判断）。
六、拓展思考
如果这道题不是 BST，而是普通二叉树，该怎么解？
答案：先遍历所有节点，将节点值存入数组，再对数组排序，计算相邻元素的最小差值。时间复杂度 O(n log n)（排序耗时），空间复杂度 O(n)（存储所有节点值），效率低于本题的解法，由此可见利用数据结构特性解题的重要性。
好了，这道题的两种解法就讲解完毕了。希望大家能通过这道题，加深对 BST 特性和二叉树中序遍历的理解，下次遇到类似题目能快速想到解题思路。
