問題概要

二分探索木の妥当性を判定する問題です。与えられた二分木のルートノードから、その木が二分探索木の条件を満たしているかどうかを確認します。

二分探索木の定義：

• 任意のノードの左部分木に含まれる値は、そのノードの値より小さい
• 任意のノードの右部分木に含まれる値は、そのノードの値より大きい
• 左右の部分木もそれぞれ二分探索木である

実行例

例1：

入力：root = [2,1,3]
出力：true

例2：

入力：root = [5,1,4,null,null,3,6]
出力：false
説明：ルートノードの値5に対して、右子ノードの値4が条件を満たさない

解法

解法1：再帰による範囲チェック

各ノードが許容範囲内にあるかを再帰的に確認します。ノードの値が指定範囲外の場合、即座にfalseを返します。

Java実装：

class Solution {
    public boolean checkBST(TreeNode node, long minBound, long maxBound) {
        if (node == null) return true;
        if (node.val <= minBound || node.val >= maxBound) return false;
        return checkBST(node.left, minBound, node.val) 
            && checkBST(node.right, node.val, maxBound);
    }
    
    public boolean isValidBST(TreeNode root) {
        return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

計算量：

• 時間計算量：O(n) - 各ノードを1回ずつ処理
• 空間計算量：O(n) - 最悪ケースで再帰の深さがnに達する

解法2：中間順走査による検証

二分探索木を中間順で走査すると、値が昇順に並びます。この性質を利用して、各ノードの値が前のノードより大きいかを確認します。

Java実装：

class Solution {
    public boolean isValidBST(TreeNode root) {
        long previous = Long.MIN_VALUE;
        Deque<TreeNode> stack = new ArrayDeque<>();
        
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            
            current = stack.pop();
            if (current.val <= previous) return false;
            previous = current.val;
            current = current.right;
        }
        return true;
    }
}

計算量：

• 時間計算量：O(n) - 全ノードを1回ずつ訪問
• 空間計算量：O(n) - スタックの最大使用量