EasyRating 1303
783. Minimum Distance Between BST Nodes
treedepth-first-searchbreadth-first-searchbinary-search-treebinary-tree
解題說明
Minimum Distance Between BST Nodes
題目描述：給定一棵二元搜尋樹（BST）的根節點，找出樹中任意兩個不同節點之間的最小差值。
解題思路：利用 BST 的中序遍歷是遞增序列這個性質。最小差值一定出現在中序遍歷的相鄰兩個節點之間。
使用中序遍歷，維護一個 prev 指標記錄前一個訪問的節點。每次訪問新節點時，計算與前一個節點值的差值，更新最小差值。
C++ 解法
複雜度分析
時間複雜度：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)。邏輯清晰但多用了一個陣列。
延伸思考
- 此題和 LeetCode 530 (Minimum Absolute Difference in BST) 是否相同？
- 如果輸入不是 BST 而是普通二元樹，該如何求任意兩節點的最小差值？
- 能否用 Morris 遍歷實現 O(1) 額外空間？