給定一棵二元樹，判斷它是否是有效的二元搜尋樹 (BST)。有效 BST 定義為：左子樹所有節點值 < 根 < 右子樹所有節點值，且左右子樹也都是 BST。
Example:
Input: root = [5,1,4,null,null,3,6] Output: false (因為 4 的左子節點 3 < 根 5，但 4 本身 < 5 不滿足右子樹條件)
Intuition
TIP
每個節點都有合法的值域範圍，遞迴傳遞上下界來驗證。
- 不能只檢查「左子 < 根 < 右子」，必須檢查整個子樹的值域
- 中序遍歷 BST 會產生嚴格遞增序列，也可以利用此性質驗證
Approaches
⭐ 1. Recursion Passing Bounds — O(n) / O(h)
- Idea: 每個節點維護 (min, max) 範圍，節點值必須在此範圍內
- Time:
O(n) - Space:
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. Inorder to Verify Increasing — O(n) / O(h)
- Idea: BST 的中序遍歷是嚴格遞增的，遍歷時檢查每個值是否大於前一個
- Time:
O(n) - Space:
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)
}
}Why Long instead of Int?
因為節點值可能是 Int.MIN_VALUE 或 Int.MAX_VALUE，如果用 Int 作為邊界會導致邊界條件判斷錯誤。使用 Long 可以避免這個問題。
🔑 Takeaways
- Pattern: 用範圍約束（上下界）驗證 BST 性質
- Key trick: BST 問題常見兩種思路：(1) 遞迴傳遞範圍 (2) 利用中序遍歷的有序性