BST 經典問題#

驗證二元搜尋樹 ↗#

中序走訪#

核心原理：BST 的中序走訪結果必為嚴格遞增序列。

fun isValidBST(root: TreeNode?): Boolean {
    var prev = Long.MIN_VALUE   // 前一個中序節點值，初始為 -∞

    fun inorder(node: TreeNode?): Boolean {
        if (node == null) return true

        if (!inorder(node.left)) return false

        if (node.value <= prev) return false   // 不是嚴格遞增
        prev = node.value.toLong()

        return inorder(node.right)
    }

    return inorder(root)
}

空間最佳化：不需存整個走訪序列，只需維護「前一個節點值」即可。

遞迴區間驗證#

傳遞允許的數值範圍 (min, max)：

fun isValidBST(root: TreeNode?): Boolean {
    // 用 Long 承載邊界，避免節點值等於 Int.MIN/MAX_VALUE 時比較失準
    fun validate(node: TreeNode?, min: Long, max: Long): Boolean {
        if (node == null) return true

        if (node.value <= min || node.value >= max) return false

        return validate(node.left, min, node.value.toLong()) &&
                validate(node.right, node.value.toLong(), max)
    }

    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
}

最近公共祖先#

普通二元樹 ↗#

使用後序走訪，自底向上回傳：

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
    if (root == null || root == p || root == q) return root

    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)

    if (left != null && right != null) return root   // p, q 分居兩側

    return left ?: right
}

精髓：回傳值具有多重含義 - 既表示「找到了 p 或 q」，也表示「找到了 LCA」。

BST 版本 ↗#

利用 BST 的排序特性，迭代實作：

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
    var node = root
    while (node != null) {
        node = when {
            p.value < node.value && q.value < node.value -> node.left   // 都在左邊
            p.value > node.value && q.value > node.value -> node.right  // 都在右邊
            else -> return node                                          // 分岔點即為 LCA
        }
    }
    return null
}

優勢：BST 版本可用迭代，空間複雜度 O(1)。

二元樹的深度：最大深度 ↗ / 最小深度 ↗#

最大深度#

fun maxDepth(root: TreeNode?): Int {
    if (root == null) return 0
    return maxOf(maxDepth(root.left), maxDepth(root.right)) + 1
}

最小深度#

陷阱：不能直接 minOf(left, right) + 1！單邊子樹為空時不算葉節點。

fun minDepth(root: TreeNode?): Int {
    if (root == null) return 0

    val left = minDepth(root.left)
    val right = minDepth(root.right)

    // 處理單邊子樹為空的情況
    if (left == 0 || right == 0) return left + right + 1

    return minOf(left, right) + 1
}
Backward 二元樹走訪 紅黑樹 Forward