Unique BSTs II - 分割統治＋区間メモ化

概要

整数 n に対し、値 1..n を持つノードで構成される構造的に一意な BST（二分探索木）をすべて生成します。

各木は BST の性質を満たす（左部分木 < 根 < 右部分木）
同型でない木はすべて列挙する（順序は任意）
1 ≤ n ≤ 8 の制約
n=8 でも生成本数はカタラン数 C₈ = 1430と小規模

🎯 戦略

分割統治（根を全列挙 → 左右部分木の直積で合成）＋区間メモ化により、重複計算を排除して出力サイズに近い計算量を実現します。

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

Python実装（LeetCode形式）

from __future__ import annotations

from typing import Dict, List, Optional, Tuple, TYPE_CHECKING

if TYPE_CHECKING:
    class TreeNode:
        val: int
        left: Optional[TreeNode]
        right: Optional[TreeNode]
        def __init__(self, val: int = 0,
                     left: Optional[TreeNode] = None,
                     right: Optional[TreeNode] = None) -> None: ...
else:
    try:
        TreeNode  # type: ignore
    except NameError:
        class TreeNode:
            """Binary Tree Node with __slots__ for memory efficiency."""
            __slots__ = ("val", "left", "right")

            def __init__(self, val: int = 0,
                         left: Optional[TreeNode] = None,
                         right: Optional[TreeNode] = None) -> None:
                self.val = val
                self.left = left
                self.right = right


class Solution:
    """
    Unique Binary Search Trees II
    1..n の値で構造的に一意な BST をすべて生成。

    Time:  ≈ O(C_n * n)  where C_n is n-th Catalan number
    Space: ≈ O(C_n * n)  (output + interval memoization)
    """

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        """
        Args:
            n: 1 <= n <= 8

        Returns:
            List of root nodes (each representing one unique BST)
        """
        if n == 0:
            return []

        # 区間 [l, r] -> 生成可能な根ノード配列
        memo: Dict[Tuple[int, int], List[Optional[TreeNode]]] = {}

        def build(l: int, r: int) -> List[Optional[TreeNode]]:
            """
            区間 [l, r] 内の値で構築可能な BST をすべて生成。
            空区間は [None]（空木1通り）で表す。
            """
            # 基底: 空区間 → 空木
            if l > r:
                return [None]

            # メモ化チェック
            key = (l, r)
            if key in memo:
                return memo[key]

            result: List[Optional[TreeNode]] = []

            # 各値を根候補として列挙
            for root_val in range(l, r + 1):
                # 左部分木: [l, root_val - 1]
                left_trees = build(l, root_val - 1)
                # 右部分木: [root_val + 1, r]
                right_trees = build(root_val + 1, r)

                # 直積で全組合せを合成
                for lt in left_trees:
                    for rt in right_trees:
                        # 新規ノード作成（部分木は参照共有）
                        node = TreeNode(root_val, lt, rt)
                        result.append(node)

            # メモに保存して返却
            memo[key] = result
            return result

        return build(1, n)

視覚的図解

分割統治フローチャート

計算量

⏱️ 時間計算量

O(Cₙ · n)

Cₙ はカタラン数（第n項）。各木の構築に O(n) の操作が必要です。メモ化により重複計算を完全に排除し、出力サイズに近い下限に到達します。

💾 空間計算量

O(Cₙ · n)

出力（全木）が支配的。アルゴリズム側は区間メモ O(n²) 個の区間に対し、各区間が最大 O(Cₙ) 本の木を保持します。

n	カタラン数 Cₙ	生成本数	実行時間
1	1	1本	即時
2	2	2本	即時
3	5	5本	即時
8	1430	1430本	<100ms