题目描述
思路解析
一句话答案：LeetCode 783 二叉搜索树节点最小距离：BST 中序遍历给出升序序列，最小差必在相邻两值间，中序走一遍用 pre 记前驱取 ans=min(ans, 当前−pre)，时间 O(n)。
给一棵 BST，任意两点差最小是多少
给定一棵二叉搜索树，也就是左小右大的那种二叉树，返回树里任意两个不同节点值之差的绝对值的最小可能值。题面这棵 root=[50,30,80,10,35,70,90]，答案是 5，来自 30 和 35 这对最接近的值。节点值互不相同、至少两个。
两两求差要比 n² 次，白费在哪
把每两个节点凑成一对求差、再挑最小，一棵 n 个节点的树有大约 n²/2 对，全比一遍是 O(n²)。这么做完全没用上 BST 的有序性：树里绝大多数点对差得很远，两个隔着好几个值的数，差不可能比它们中间夹着的相邻两数更小，比它们纯属浪费。
为什么最小差一定藏在相邻两值之间
BST 有一条硬性质：中序遍历，也就是按左子树、根、右子树的顺序访问，得到的是一串从小到大的升序值。既然值已经排成有序队列，两个数在队列里隔得越远、差只会越大；真正可能最小的差，只会出现在队列里紧挨着的两个数之间。于是问题从「两两比」缩成「把中序序列相邻两项的差各算一遍、取最小」，一趟遍历就够。
中序走一遍，pre 记前驱、ans 收最小
具体做法是一次中序 DFS，也就是顺着树一条路走到底再回头：递归进左子树，回到当前节点时结算，再递归进右子树。结算要拿当前值和它在升序序列里的前一个值作差，所以额外备一个变量 pre 记住上一个访问到的节点值。每访问一个节点就更新 ans=min(ans, 当前值−pre)，再把 pre 换成当前值。
pre 初始设成负无穷，这样第一个节点算出的差是无穷大、压不动答案，它只负责给 pre 起个头；ans 初始设成正无穷，等着被真实的差一点点顶下来。
拿 [50,30,80,10,35,70,90] 逐项收相邻差
从根 50 往左钻到 30、再到 10，10 没有左子树，成了中序第一个访问到的节点。此时 pre 还是负无穷，算出的差是无穷大，ans 不动，只把 pre 记成 10。回到 30：ans=min(∞, 30−10)=20，pre=30。转进 30 的右孩子 35：ans=min(20, 35−30)=5，pre=35，最小差头一回被压到 5。
接着回到根 50：ans=min(5, 50−35)=15 里 5 更小，ans 保持 5，pre=50。转向右子树，先到左孩子 70：ans=min(5, 70−50)=20，仍是 5；再到 80：80−70=10；最后 90：90−80=10，都没能压过 5。整条中序序列是 10、30、35、50、70、80、90，相邻差依次 20、5、15、20、10、10，最小的 5 来自 30 与 35，这就是答案。
一遍中序为什么是 O(n)，还有两处易错
每个节点只在中序里被访问一次，一次减法加一次取最小，时间 O(n)；递归吃的是调用栈，栈深随树高 h 变：均衡时约 O(log n)，塌成单链就到 O(n)，空间 O(h)。
两个地方最容易栽：pre 若初始设成 0 或某个真实值，第一个节点会算出一个假的差把答案带偏，得设成负无穷让它空转一轮；访问顺序也不能乱，一旦不是严格的左、根、右，中序序列就不再升序，只比相邻两数这套逻辑当场失效。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「中序升序、只比相邻、pre 记前驱、ans 取最小」，下面每帧都在套它。
准备 · BST 中序升序：这是一棵二叉搜索树。它的中序遍历（左、根、右）得到的是从小到大的有序序列，所以任意两点的最小差，必定落在排序后相邻的两个值之间。我们从根 50 出发，先一路向左，去找最小的那个节点。
下探 · 50 走向左孩子 30：还轮不到 50，因为它的左子树没走完。沿左边往下，走到左孩子 30，继续找更小、更靠左的节点。
下探 · 30 走向左孩子 10：还轮不到 30，因为它的左子树没走完。沿左边往下，走到左孩子 10，继续找更小、更靠左的节点。
访问 · 中序轮到 10：中序讲究左、根、右。10 的左子树已经全部走完，现在轮到它自己，把 10 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 10 是起点：10 是中序序列的第一个，也就是整棵树里最小的值。它前面没有前驱，做不了差，我们只把 pre 记成 10，等下一个节点来和它比。
访问 · 中序轮到 30：中序讲究左、根、右。30 的左子树已经全部走完，现在轮到它自己，把 30 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 30 减 10 = 20：轮到结算：用当前值 30 减去前驱 10，相邻差是 20。它比之前的最小差 无穷大 还小，把 ans 刷新成 20。 然后把 pre 更新成 30，继续往后走。
下探 · 30 走向右孩子 35：30 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 35，那边的值都比 30 大。
访问 · 中序轮到 35：中序讲究左、根、右。35 的左子树已经全部走完，现在轮到它自己，把 35 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 35 减 30 = 5：轮到结算：用当前值 35 减去前驱 30，相邻差是 5。它比之前的最小差 20 还小，把 ans 刷新成 5。 然后把 pre 更新成 35，继续往后走。
访问 · 中序轮到 50：中序讲究左、根、右。50 的左子树已经全部走完，现在轮到它自己，把 50 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 50 减 35 = 15：轮到结算：用当前值 50 减去前驱 35，相邻差是 15。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 50，继续往后走。
下探 · 50 走向右孩子 80：50 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 80，那边的值都比 50 大。
下探 · 80 走向左孩子 70：还轮不到 80，因为它的左子树没走完。沿左边往下，走到左孩子 70，继续找更小、更靠左的节点。
访问 · 中序轮到 70：中序讲究左、根、右。70 的左子树已经全部走完，现在轮到它自己，把 70 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 70 减 50 = 20：轮到结算：用当前值 70 减去前驱 50，相邻差是 20。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 70，继续往后走。
访问 · 中序轮到 80：中序讲究左、根、右。80 的左子树已经全部走完，现在轮到它自己，把 80 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 80 减 70 = 10：轮到结算：用当前值 80 减去前驱 70，相邻差是 10。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 80，继续往后走。
下探 · 80 走向右孩子 90：80 已经访问并结算完了，标成蓝色。按中序规矩，接着去它的右子树，走向右孩子 90，那边的值都比 80 大。
访问 · 中序轮到 90：中序讲究左、根、右。90 的左子树已经全部走完，现在轮到它自己，把 90 记进中序序列。它就是当前升序序列里最新的一个。
结算 · 90 减 80 = 10：轮到结算：用当前值 90 减去前驱 80，相邻差是 10。它没比当前最小差 5 更小，ans 保持 5 不变。 然后把 pre 更新成 90，继续往后走。
完成 · 答案 = 5：中序序列是 10、30、35、50、70、80、90，确实从小到大。相邻差依次是 20、5、15、20、10、10，最小的是 30 和 35 之间的 5，这就是答案。我们没有两两枚举所有节点对，只靠 BST 中序有序、比了相邻几对就锁定了结果。
题目保证至少两个节点，不会空树。两节点时只有一个差；若出现相等的相邻值，最小差就是 0。
面试重点：和 530 同题、非 BST 要排序、以及迭代或 Morris 的空间优化。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def minDiffInBST(self, root: Optional[TreeNode]) -> int: def dfs(root: Optional[TreeNode]): if root is None: return dfs(root.left) nonlocal pre, ans ans = min(ans, root.val - pre) pre = root.val dfs(root.right) pre = -inf ans = inf dfs(root) return ans复杂度
- 时间：O(n)，中序遍历每个节点恰好访问一次，每次只做一次减法和比较
- 空间：O(h)，递归栈深 = 树高 h；最坏退化成链时 O(n)，平衡时 O(log n)
易错点
面试追问把动画讲成自己的话
追问这题和 530「二叉搜索树的最小绝对差」是不是一样？
追问如果给的不是 BST，而是普通二叉树呢？
追问能不能不用递归、把空间压到 O(1)？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
叶子相似的树
LeetCode 872 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题