783. Minimum Distance Between BST Nodes

Easy
Description

給定一棵 BST 的根節點，回傳任意兩個不同節點之間的最小差值。此最小差值一定出現在中序遍歷的相鄰節點之間。

Example:

Input: root = [4,2,6,1,3] Output: 1 (相鄰節點 2 和 3 的差值)

Intuition#

BST 的中序遍歷產生有序序列，最小差值一定出現在相鄰元素之間。

  • BST 中序遍歷是嚴格遞增的
  • 最小差值只可能出現在排序後的相鄰元素之間，因此只需要在中序遍歷時比較當前節點與前一個節點的差值

Approaches#

⭐ 1: 中序遍歷 (Recursive)#

  • 概念: 中序遍歷 BST，持續追蹤前一個節點值，比較相鄰差值取最小
  • 時間複雜度: O(n)，遍歷所有節點
  • 空間複雜度: 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: 中序遍歷 (Iterative)#

  • 概念: 用 Stack 迭代中序遍歷，同樣追蹤前一個值比較差值
  • 時間複雜度: O(n)
  • 空間複雜度: 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 的有序性質將問題轉化為有序序列問題
  • 關鍵技巧: BST 中任意兩節點的最小差值一定在中序遍歷的相鄰節點間，不需要兩兩比較