問題の概要

二分探索木（BST）が有効であるかどうかを判定するには、各ノードが以下の条件を満たしているかを確認する必要があります。

• ノードの左部分木に含まれるすべての値は、そのノードの値より厳密に小さい。
• ノードの右部分木に含まれるすべての値は、そのノードの値より厳密に大きい。
• 左右の部分木もそれぞれ二分探索木でなければならない。

これを効率的にチェックするために、二分探索木の重要な性質である「中間順走査（In-order Traversal）を行うと値が昇順に並ぶ」という特性を利用します。

実装：再帰的な中間順走査

以下のC++コードは、中間順走査を行いながら、現在のノードの値が直前に訪れたノードの値よりも大きいかを検証します。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    // 直前に訪問したノードへのポインタ
    TreeNode* lastNode = nullptr;

    // 中間順走査を用いてソート順を検証するヘルパー関数
    bool checkSequence(TreeNode* current) {
        // ベースケース：空のノードは有効
        if (current == nullptr) return true;

        // 1. 左部分木を探索
        if (!checkSequence(current->left)) return false;

        // 2. 現在のノードの値をチェック
        // 直前のノードが存在し、その値が現在の値以上であればBSTではない
        if (lastNode != nullptr && lastNode->val >= current->val) {
            return false;
        }

        // 直前のノードを更新
        lastNode = current;

        // 3. 右部分木を探索
        return checkSequence(current->right);
    }

public:
    bool isValidBST(TreeNode* root) {
        return checkSequence(root);
    }
};

実行フローの詳細

このアルゴリズムの動作を理解するために、2つのケースを見ていきましょう。

ケース1：有効なBST

入力: root = [2,1,3]
    2
   / \
  1   3

1. checkSequence(2) が呼び出され、まず左部分木 checkSequence(1) へ進みます。
2. checkSequence(1) では左部分木が null なので戻り、lastNode は null のためチェックをパスします。lastNode を 1 に更新し、右部分木（null）をチェックして true を返します。
3. checkSequence(2) に戻り、現在値 2 と lastNode (1) を比較します。1 < 2 なので条件を満たします。lastNode を 2 に更新します。
4. 右部分木 checkSequence(3) へ進みます。3 と 2 を比較し、2 < 3 なので条件を満たします。
5. すべてのチェックで true が返されたため、結果は true となります。

ケース2：無効なBST

入力: root = [5,1,4,null,null,3,6]
      5
     / \
    1   4
       / \
      3   6

1. 中間順走査により、ノードは 1 -> 5 -> 3 -> 4 -> 6 の順にアクセスされます。
2. 最初に 1 が処理され、次に 5 が処理されます。lastNode は 5 になります。
3. 次に 5 の右部分木である 4 へ移動し、その左の子である 3 が処理されます。
4. ここで、現在値 3 と lastNode (5) を比較します。3 は 5 より小さいため、二分探索木の条件（右部分木は親より大きい）に違反します。
5. 関数は false を返し、処理が終了します。

別解：反復的なアプローチ（スタックを使用）

再帰を使用せず、スタックを用いて明示的に中間順走査を実装することも可能です。これにより、再帰の深さによるスタックオーバーフローのリスクを回避できます。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        std::stack nodeStack;
        TreeNode* prev = nullptr;
        TreeNode* curr = root;

        while (curr != nullptr || !nodeStack.empty()) {
            // 左端のノードまで降りていく
            while (curr != nullptr) {
                nodeStack.push(curr);
                curr = curr->left;
            }

            // スタックからノードを取り出す（中間順の訪問）
            curr = nodeStack.top();
            nodeStack.pop();

            // 前のノードとの大小関係をチェック
            if (prev != nullptr && prev->val >= curr->val) {
                return false;
            }

            prev = curr;
            // 右部分木へ移動
            curr = curr->right;
        }
        return true;
    }
};

計算複雑性

解法のポイント

• 前駆ノードの保持: lastNode（または pre）変数を使用して、前回の走訪時のノードを記録します。これにより、現在のノードが前のノードよりも大きい値を持っているかを O(1) で判定できます。
• 中間順走査の特性: BSTの定義上、中間順走査による出力列は厳密に単調増加（昇順）でなければなりません。この性質を利用することで、各ノードに対して範囲（min, max）を持ち回る手法よりも実装が簡潔になります。