NeetCode #430LC-783EasyTrees
← Back to All Problems#430 · #783 · Minimum Distance Between BST Nodes(二叉搜索树节点最小距离)
📌 Problem Statement & Constraints
Given the root of a binary search tree, return the minimum difference between the values of any two distinct nodes. Constraints: the number of nodes is in
[2, 100], 0 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- An in-order traversal of a BST visits the values in ascending order.
- The minimum difference must therefore occur between adjacent values in that order.
- Track the previous visited value and update the minimum gap.
- This is O(n) instead of the O(n log n) sort-the-values approach.
💻 Benchmark Python3 Implementation
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
self.prev = None
self.best = float("inf")
def inorder(node: Optional[TreeNode]) -> None:
if not node:
return
inorder(node.left)
if self.prev is not None:
self.best = min(self.best, node.val - self.prev) # adjacent pair
self.prev = node.val
inorder(node.right)
inorder(root)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Comparing all pairs: O(n^2), and unnecessary given the sorted order.
- Sorting the values and scanning: O(n log n); the in-order traversal already yields the sorted order.
- Forgetting the
prev is not Noneguard: the first visited node has no predecessor. - Assuming the tree is balanced: the recursion depth can reach n for a degenerate BST.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Trees Problems
中文速览与面试要点
二叉搜索树节点最小距离
给你一个二叉搜索树的根节点 root,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。约束:树中节点的数目范围是 [2, 100];0 ≤ Node.val ≤ 10^5。
核心要点
- 中序遍历 + 相邻比较(标准解) :BST 的中序遍历是升序序列,因此最小差值必然出现在 相邻 两个节点之间。
- 实现 :递归中序,用变量 prev 记录前一个访问的值,每步用 node.val − prev 更新最优。
- 为什么只需比较相邻 :升序序列中,任意两数的差至少为它们之间相邻差之和,因此最小值必在相邻对中取得。
- 复杂度 :O(n) 时间、O(h) 空间。
常见陷阱
- 比较所有节点对 :O(n²)。中序相邻比较即可。
- 忘记 prev is not None 的判断 :第一个节点没有前驱。
- prev 忘记用 nonlocal 声明 :会创建局部变量,导致每层递归各自独立。
- 用 abs(node.val − prev) :中序升序,差必为正,无需取绝对值。
参考实现
class Solution:
def minDiffInBST(self, root: 'TreeNode') -> int:
prev = None
best = float('inf')
def inorder(node):
nonlocal prev, best
if not node:
return
inorder(node.left)
if prev is not None:
diff = node.val - prev # 中序升序,差必为正
if diff < best:
best = diff
prev = node.val
inorder(node.right)
inorder(root)
return best