Validate Binary Search Tree (BST 驗證)

LC 98 題意

• 給定一棵二元樹，判斷它是否是一棵有效的二元搜尋樹（BST）。
• BST 的定義：
  • 左子樹所有節點都 小於 根節點。
  • 右子樹所有節點都 大於 根節點。
  • 左右子樹皆為 BST。
• Example
  Input: [2,1,3]
  Output: true

thoughts

• 遞迴方式 (DFS) + 區間限制
  • 傳入 (node, min, max) 範圍。
  • 節點值需滿足 min < node.val < max。
  • 遞迴檢查左右子樹。
• 中序遍歷法
  • 若中序遍歷結果是嚴格遞增，則為 BST。

Kotlin — 區間遞迴法

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        fun dfs(node: TreeNode?, min: Long, max: Long): Boolean {
            if (node == null) return true
            if (node.`val` <= min || node.`val` >= max) return false
            return dfs(node.left, min, node.`val`.toLong()) &&
                   dfs(node.right, node.`val`.toLong(), max)
        }
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }
}

Follow-up

• 若樹節點非常多（深度 > 10^5），如何避免 StackOverflow？
  • → 改用 中序迭代法。
• 若要同時計算節點數或樹高，能否在同一次 DFS 完成？
  • → 可以，多傳遞狀態即可。
• 如何處理包含重複值的 BST（≤ or ≥）？