LeetCode 530简单二叉搜索树
二叉搜索树的最小绝对差 图解题解
这道题到底在问什么
给一棵 BST 的根节点，返回树中任意两个不同节点的值，相减取绝对值后的最小结果。
- 输入
- BST 如图（14 个节点）
- 输出
- 1
最优解：一步一步想明白
- 3核心一句话：BST 中序 = 升序，最小绝对差一定来自中序相邻两数，边遍历边比相邻差。
- 4完整的 BST。中序遍历从最左下角开始，按「左子树 → 根 → 右子树」访问，得到升序序列。我们维护一个 prev（上一个访问的值）和 minDiff（目前最小相邻差）。
- 5中序怎么找下一个？从根一路向左压栈，走到最左下角。当前定位到节点 2（它是所有未访问节点里最小的）。下一步把它和前驱（暂无前驱）比一下相邻差。
- 6中序第一个访问到的就是最小值 2（橙色）。它还没有前驱，先把它存进 prev，暂时不算差。
- 7节点 2 记为前驱（蓝色=已访问）。还没有相邻差可比，继续中序走下一个更大的数。
- 8中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 4（它是所有未访问节点里最小的）。下一步把它和前驱 2比一下相邻差。
- 9中序访问到 4（橙色），它的前驱是 2（也是橙色）。两者在升序里相邻，算相邻差：|4 - 2| = 2。
- 10相邻差 2 比之前的最小差更小！更新 minDiff = 2。节点 4 记为新的前驱（蓝色），继续往后走。
- 11中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 6（它是所有未访问节点里最小的）。下一步把它和前驱 4比一下相邻差。
- 12中序访问到 6（橙色），它的前驱是 4（也是橙色）。两者在升序里相邻，算相邻差：|6 - 4| = 2。
- 13相邻差 2 没比当前 minDiff = 2 更小，minDiff 不变。节点 6 记为前驱（蓝色），继续中序走下一个。
- 14中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 9（它是所有未访问节点里最小的）。下一步把它和前驱 6比一下相邻差。
- 15中序访问到 9（橙色），它的前驱是 6（也是橙色）。两者在升序里相邻，算相邻差：|9 - 6| = 3。
- 16相邻差 3 没比当前 minDiff = 2 更小，minDiff 不变。节点 9 记为前驱（蓝色），继续中序走下一个。
- 17中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 11（它是所有未访问节点里最小的）。下一步把它和前驱 9比一下相邻差。
- 18中序访问到 11（橙色），它的前驱是 9（也是橙色）。两者在升序里相邻，算相邻差：|11 - 9| = 2。
- 19相邻差 2 没比当前 minDiff = 2 更小，minDiff 不变。节点 11 记为前驱（蓝色），继续中序走下一个。
- 20中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 13（它是所有未访问节点里最小的）。下一步把它和前驱 11比一下相邻差。
- 21中序访问到 13（橙色），它的前驱是 11（也是橙色）。两者在升序里相邻，算相邻差：|13 - 11| = 2。
- 22相邻差 2 没比当前 minDiff = 2 更小，minDiff 不变。节点 13 记为前驱（蓝色），继续中序走下一个。
- 23中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 14（它是所有未访问节点里最小的）。下一步把它和前驱 13比一下相邻差。
- 24中序访问到 14（橙色），它的前驱是 13（也是橙色）。两者在升序里相邻，算相邻差：|14 - 13| = 1。
- 25相邻差 1 比之前的最小差更小！更新 minDiff = 1。节点 14 记为新的前驱（蓝色），继续往后走。
- 26中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 20（它是所有未访问节点里最小的）。下一步把它和前驱 14比一下相邻差。
- 27中序访问到 20（橙色），它的前驱是 14（也是橙色）。两者在升序里相邻，算相邻差：|20 - 14| = 6。
- 28相邻差 6 没比当前 minDiff = 1 更小，minDiff 不变。节点 20 记为前驱（蓝色），继续中序走下一个。
- 29中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 21（它是所有未访问节点里最小的）。下一步把它和前驱 20比一下相邻差。
- 30中序访问到 21（橙色），它的前驱是 20（也是橙色）。两者在升序里相邻，算相邻差：|21 - 20| = 1。
- 31相邻差 1 没比当前 minDiff = 1 更小，minDiff 不变。节点 21 记为前驱（蓝色），继续中序走下一个。
- 32中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 22（它是所有未访问节点里最小的）。下一步把它和前驱 21比一下相邻差。
- 33中序访问到 22（橙色），它的前驱是 21（也是橙色）。两者在升序里相邻，算相邻差：|22 - 21| = 1。
- 34相邻差 1 没比当前 minDiff = 1 更小，minDiff 不变。节点 22 记为前驱（蓝色），继续中序走下一个。
- 35中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 23（它是所有未访问节点里最小的）。下一步把它和前驱 22比一下相邻差。
- 36中序访问到 23（橙色），它的前驱是 22（也是橙色）。两者在升序里相邻，算相邻差：|23 - 22| = 1。
- 37相邻差 1 没比当前 minDiff = 1 更小，minDiff 不变。节点 23 记为前驱（蓝色），继续中序走下一个。
- 38中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 25（它是所有未访问节点里最小的）。下一步把它和前驱 23比一下相邻差。
- 39中序访问到 25（橙色），它的前驱是 23（也是橙色）。两者在升序里相邻，算相邻差：|25 - 23| = 2。
- 40相邻差 2 没比当前 minDiff = 1 更小，minDiff 不变。节点 25 记为前驱（蓝色），继续中序走下一个。
- 41中序怎么找下一个？弹回栈顶的父节点（左子树已数完）。当前定位到节点 28（它是所有未访问节点里最小的）。下一步把它和前驱 25比一下相邻差。
- 42中序访问到 28（橙色），它的前驱是 25（也是橙色）。两者在升序里相邻，算相邻差：|28 - 25| = 3。
- 43相邻差 3 没比当前 minDiff = 1 更小，minDiff 不变。节点 28 记为前驱（蓝色），继续中序走下一个。
- 44中序怎么找下一个？从上一个节点转向它的右子树，再一路向左到底。当前定位到节点 31（它是所有未访问节点里最小的）。下一步把它和前驱 28比一下相邻差。
- 45中序访问到 31（橙色），它的前驱是 28（也是橙色）。两者在升序里相邻，算相邻差：|31 - 28| = 3。
- 46相邻差 3 没比当前 minDiff = 1 更小，minDiff 不变。节点 31 记为前驱（蓝色），继续中序走下一个。
- 47中序走完整棵树，升序序列里相邻差最小的一对是 13 和 14（绿色），|14 - 13| = 1。这就是全树任意两点的最小绝对差 —— 不必两两比较，只看升序相邻就够。
⚠️ 容易写错的地方
✗ 错：两两节点都比一遍求差
✓ 对：只比中序相邻两数的差
升序里最小差必在相邻对，两两比是 O(n²) 多余
✗ 错：忘了维护前驱 prev / 用错初值
✓ 对：prev 初始为空，第一个节点只存不比
没有前驱时算差会得到错误的差值
✗ 错：用前序/后序遍历再比相邻
✓ 对：必须中序（左→根→右）
只有中序遍历 BST 才得到升序，相邻才有意义
完整代码（Python / C++ / Java）
Python
def getMinimumDifference(root):
stack, cur = [], root
prev = None
ans = float("inf")
while stack or cur:
while cur: # 一路向左
stack.append(cur)
cur = cur.left
cur = stack.pop() # 中序访问 cur
if prev is not None:
ans = min(ans, cur.val - prev)
prev = cur.val # 更新前驱
cur = cur.right
return ansC++
int getMinimumDifference(TreeNode* root){
stack<TreeNode*> st;
TreeNode* cur = root;
long prev = -1, ans = LONG_MAX;
while(!st.empty() || cur){
while(cur){ st.push(cur); cur = cur->left; }
cur = st.top(); st.pop(); // 中序访问
if(prev != -1) ans = min(ans, (long)cur->val - prev);
prev = cur->val;
cur = cur->right;
}
return (int)ans;
}Java
public int getMinimumDifference(TreeNode root){
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
Integer prev = null;
int ans = Integer.MAX_VALUE;
while(!stack.isEmpty() || cur != null){
while(cur != null){ stack.push(cur); cur = cur.left; }
cur = stack.pop(); // 中序访问
if(prev != null) ans = Math.min(ans, cur.val - prev);
prev = cur.val; // 更新前驱
cur = cur.right;
}
return ans;复杂度
时间
O(n)
中序遍历每个节点恰好访问一次
空间
O(H)
栈最多存一条从根到叶的路径，H 为树高
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树的最小绝对差 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果不是 BST，是普通二叉树，求任意两点最小绝对差怎么做？+
普通树没有升序性质，最直接是先遍历收集所有值，排序后扫相邻差取最小，时间 O(n log n)。或把值放进有序集合 / 桶，本质都要先排序拿到升序再比相邻。
如果要求最大绝对差呢？+
最大绝对差 = 最大值 - 最小值。在 BST 里就是最右下角节点值减最左下角节点值，一次找最左、一次找最右即可，O(H)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二叉搜索树的最小绝对差 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。