給定一棵 BST 的根節點，回傳任意兩個不同節點之間的最小差值。此最小差值一定出現在中序遍歷的相鄰節點之間。
Example:
Input: root = [4,2,6,1,3] Output: 1 (相鄰節點 2 和 3 的差值)
Intuition
TIP
BST 的中序遍歷產生有序序列，最小差值一定出現在相鄰元素之間。
- BST 中序遍歷是嚴格遞增的
- 最小差值只可能出現在排序後的相鄰元素之間，因此只需要在中序遍歷時比較當前節點與前一個節點的差值
Approaches
⭐ 1. Inorder (recursive) — O(n) / O(h)
- Idea: 中序遍歷 BST，持續追蹤前一個節點值，比較相鄰差值取最小
- Time:
O(n)，遍歷所有節點 - Space:
O(h)，遞迴堆疊深度
class Solution {
private var prev: Int? = null
private var minDiff = Int.MAX_VALUE
fun minDiffInBST(root: TreeNode?): Int {
prev = null
minDiff = Int.MAX_VALUE
inorder(root)
return minDiff
}
private fun inorder(node: TreeNode?) {
if (node == null) return
inorder(node.left)
prev?.let { minDiff = minOf(minDiff, node.`val` - it) }
prev = node.`val`
inorder(node.right)
}
}2. Inorder (iterative) — O(n) / O(h)
- Idea: 用 Stack 迭代中序遍歷，同樣追蹤前一個值比較差值
- Time:
O(n) - Space:
O(h)
class Solution {
fun minDiffInBST(root: TreeNode?): Int {
var minDiff = Int.MAX_VALUE
var prev: Int? = null
val stack = ArrayDeque<TreeNode>()
var curr = root
while (curr != null || stack.isNotEmpty()) {
while (curr != null) {
stack.addLast(curr)
curr = curr.left
}
curr = stack.removeLast()
prev?.let { minDiff = minOf(minDiff, curr!!.`val` - it) }
prev = curr!!.`val`
curr = curr.right
}
return minDiff
}
}🔑 Takeaways
- Pattern: BST + 中序遍歷 — 利用 BST 的有序性質將問題轉化為有序序列問題
- Key trick: BST 中任意兩節點的最小差值一定在中序遍歷的相鄰節點間，不需要兩兩比較