98. Validate Binary Search Tree

Medium

Description

給定一棵二元樹，判斷它是否是有效的二元搜尋樹 (BST)。有效 BST 定義為：左子樹所有節點值 < 根 < 右子樹所有節點值，且左右子樹也都是 BST。

Example:

Input: root = [5,1,4,null,null,3,6] Output: false (因為 4 的左子節點 3 < 根 5，但 4 本身 < 5 不滿足右子樹條件)

Intuition#

每個節點都有合法的值域範圍，遞迴傳遞上下界來驗證。

不能只檢查「左子 < 根 < 右子」，必須檢查整個子樹的值域
中序遍歷 BST 會產生嚴格遞增序列，也可以利用此性質驗證

Approaches#

⭐ 1: 遞迴傳遞上下界#

概念: 每個節點維護 (min, max) 範圍，節點值必須在此範圍內
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }

    private fun validate(node: TreeNode?, min: Long, max: Long): Boolean {
        if (node == null) return true
        if (node.`val` <= min || node.`val` >= max) return false
        return validate(node.left, min, node.`val`.toLong()) &&
               validate(node.right, node.`val`.toLong(), max)
    }
}

2: 中序遍歷驗證遞增#

概念: BST 的中序遍歷是嚴格遞增的，遍歷時檢查每個值是否大於前一個
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    private var prev: Long = Long.MIN_VALUE

    fun isValidBST(root: TreeNode?): Boolean {
        prev = Long.MIN_VALUE
        return inorder(root)
    }

    private fun inorder(node: TreeNode?): Boolean {
        if (node == null) return true
        if (!inorder(node.left)) return false
        if (node.`val`.toLong() <= prev) return false
        prev = node.`val`.toLong()
        return inorder(node.right)
    }
}

為什麼用 Long 而不是 Int？

因為節點值可能是 Int.MIN_VALUE 或 Int.MAX_VALUE，如果用 Int 作為邊界會導致邊界條件判斷錯誤。使用 Long 可以避免這個問題。

🔑 Takeaways#

Pattern: 用範圍約束（上下界）驗證 BST 性質
關鍵技巧: BST 問題常見兩種思路：(1) 遞迴傳遞範圍 (2) 利用中序遍歷的有序性