題目描述:給定一棵二元搜尋樹(BST)的根節點,找出樹中任意兩個不同節點之間的最小差值。
解題思路:利用 BST 的中序遍歷是遞增序列這個性質。最小差值一定出現在中序遍歷的相鄰兩個節點之間。
使用中序遍歷,維護一個 prev 指標記錄前一個訪問的節點。每次訪問新節點時,計算與前一個節點值的差值,更新最小差值。
時間複雜度:O(n) — 中序遍歷每個節點恰好一次。
空間複雜度:O(h) — 遞迴堆疊深度等於樹的高度,平衡樹為 O(log n),最壞為 O(n)。
1. Initialize minDiff = INF, prev = null
2. Perform in-order traversal:
a. Recurse left
b. If prev is not null:
- minDiff = min(minDiff, node.val - prev.val)
c. prev = current node
d. Recurse right
3. Return minDiff迭代中序遍歷:用顯式堆疊模擬中序遍歷,避免遞迴。時間 O(n),空間 O(h)。適合樹很深的場景。
中序遍歷存入陣列:先將所有值按中序存入陣列,再線性掃描相鄰差值。時間 O(n),空間 O(n)。邏輯清晰但多用了一個陣列。