Validate Binary Search Tree

アルゴリズム概要

問題の説明

二分木の根ノードが与えられたとき、それが有効なBST（Binary Search Tree）であるかを判定します。

入出力例

Input: root = [2,1,3]
    2
   / \
  1   3
Output: true

Input: root = [5,1,4,null,null,3,6]
      5
     / \
    1   4
       / \
      3   6
Output: false (4は5より小さいべき)

制約条件

• ノード数: 1 ≤ n ≤ 10^4
• ノード値: -2^31 ≤ Node.val ≤ 2^31 - 1

戦略

主要ポイント

• 時間計算量: O(n) - 全ノードを1回ずつ訪問
• 空間計算量: O(h) - スタックの深さは木の高さ（最悪O(n)、平衡木でO(log n)）
• 最適化: 全要素を配列に格納せず、prevのみで比較
• 安全性: 再帰を使わないため、深い木でもスタックオーバーフローなし

ステップバイステップ解説

Python実装

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        """
        反復的な中順巡回でBSTを検証

        時間計算量: O(n)
        空間計算量: O(h) where h is tree height
        """
        stack: List[TreeNode] = []
        cur: Optional[TreeNode] = root
        prev: Optional[int] = None

        # ローカル束縛による最適化
        push = stack.append
        pop = stack.pop

        while cur is not None or stack:
            # 左部分木を全てスタックに積む
            while cur is not None:
                push(cur)
                cur = cur.left

            # 最左端のノードを取り出す
            node = pop()
            val = node.val

            # 厳密単調増加チェック
            if prev is not None and val <= prev:
                return False

            # prev を更新
            prev = val

            # 右部分木へ移動
            cur = node.right

        return True

フローチャート

フローの説明：
1. スタック、cur、prevを初期化
2. 緑の矢印（はい）：curがNoneでないかスタックに要素があればループ継続
3. 左部分木探索：curがNoneでない限りスタックに積み、左へ移動
4. 赤の矢印（いいえ）：最左端到達後、ノードを取り出す
5. BST違反チェック：val ≤ prev なら即座にFalse返却
6. 紫の矢印（ループバック）：prevを更新後、右部分木へ移動してループ再開
7. 全ノード通過でTrueを返却

計算量分析

代替手法との比較