28. Validate Binary Search Tree

読了目安 約2分

Tree / LC 98 (Medium) — BST の検証。値の範囲を上から伝える再帰。

問題

LeetCode 98. Validate Binary Search Tree（Medium / カテゴリ: Tree）

二分木の根 root が与えられるので、正しい二分探索木（BST）かを判定します。 条件は、各ノードについて「左の部分木のすべての値 < ノードの値 < 右の部分木のすべての値」です。 等しい値は許されません。 このページのテストでは、ノードの値として Int.min や Int.max も現れます。

考え方

Swift 実装のポイント

• 下限・上限を Int.min / Int.max の番兵で初期化すると、ノードの値がちょうど Int.min / Int.max のときに誤判定します。範囲は Int? で持ち、nil を「制限なし」と扱うのが安全です。
• 比較は「下限 < 値 < 上限」の狭義の不等号です。等しい値は BST に許されません。
• if let low = low, node.val <= low { return false } の形で、オプショナルの下限を自然に検査できます。

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        func valid(_ node: TreeNode?, _ low: Int?, _ high: Int?) -> Bool {
            guard let node = node else { return true }
            if let low = low, node.val <= low { return false }
            if let high = high, node.val >= high { return false }
            return valid(node.left, low, node.val) && valid(node.right, node.val, high)
        }
        return valid(root, nil, nil)
    }
}