アルゴリズム概要

💡 この問題を一言で言うと

昇順ソート済みリストを受け取り、左右の部分木の高さの差が常に 1 以下（＝高さ平衡）になる二分探索木（BST）のルートノードを返す問題です。「真ん中の要素を根にする」という発想が核心で、これを再帰的に繰り返すことで自然に平衡が実現されます。

⚠️ なぜ単純な挿入では解けないのか

  • 端から順に insert() を繰り返すと、毎回右の子に追加されて「竹のような一本道の木」になり、高さが O(n) になる
  • 高さ平衡の条件を満たすには、どの値を根に選ぶかを戦略的に決める必要がある
  • スライス nums[:mid] を使うと再帰ごとにリストコピーが発生し、空間計算量が O(n log n) に悪化する
O(n)
時間計算量
O(log n)
空間計算量
分割統治法
アルゴリズム
再帰
実装方式

入出力例 1

入力: nums = [-10, -3, 0, 5, 9]

出力: [0, -3, 9, -10, null, 5]

→ 配列の中央 0（インデックス2）を根にすることで、左右に各2要素ずつ分配でき、高さ平衡が実現されます。

入出力例 2

入力: nums = [1, 3]

出力: [3, 1] または [1, null, 3]

→ 2要素の場合、中央インデックス mid = (0+1)//2 = 0 なので 1 が根になります。どちらの形も正解として受理されます。

📌 制約

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums は厳密な昇順（重複なし）

Python 実装

📋 このコードの構造（先に全体像を把握しよう）

  1. ネスト関数 build(lo, hi) を定義して nums を引数なしで参照できるようにする
  2. ベースケース：lo > hi なら None を返して再帰終了
  3. 中央インデックス mid = (lo + hi) // 2 を計算して根ノードを作成
  4. 左半分・右半分を再帰的に構築して左右の子に接続し、ノードを返す
from typing import Optional

# LeetCode が提供する TreeNode クラス（定義済みとして扱う）
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sortedArrayToBST(self, nums: list[int]) -> Optional["TreeNode"]:
        def build(lo: int, hi: int) -> Optional["TreeNode"]:
            # ベースケース：lo > hi のとき空区間 → None を返して再帰終了
            # この条件がないと無限ループになり RuntimeError が発生する
            if lo > hi:
                return None

            # 中央インデックスを床除算（//）で計算する
            # スライス nums[lo:hi] を使わないのは、新しいリストのコピーが発生して
            # 空間計算量が O(n log n) に悪化するため。インデックスなら O(1)。
            mid = (lo + hi) // 2

            # 中央の値でノードを作成（このノードが現在の区間の「根」になる）
            # nums[mid] を根にすることで左右の要素数の差が常に 1 以下に保たれる
            node = TreeNode(nums[mid])

            # 左半分 [lo, mid-1] で左部分木を再帰構築
            # mid 自体は現在のノードとして使用済みのため含まない（mid-1 まで）
            node.left = build(lo, mid - 1)

            # 右半分 [mid+1, hi] で右部分木を再帰構築
            node.right = build(mid + 1, hi)

            # 左右の子ノードが接続された完成ノードを返す
            return node

        # 全体の範囲（インデックス 0 〜 最後のインデックス）で再帰を開始
        return build(0, len(nums) - 1)

▶ 入力例 nums = [-10, -3, 0, 5, 9] での動作トレース 

build(0, 4):
  mid = 2 → node = TreeNode(0)    ← 根ノード確定！
  node.left  = build(0, 1)
    mid = 0 → node = TreeNode(-10)
    node.left  = build(0, -1) → lo(0) > hi(-1) → None
    node.right = build(1, 1)
      mid = 1 → node = TreeNode(-3) ← 葉ノード
      return TreeNode(-3)
    return TreeNode(-10, left=None, right=TreeNode(-3))
  node.right = build(3, 4)
    mid = 3 → node = TreeNode(5)
    node.left  = build(3, 2) → lo(3) > hi(2)  → None
    node.right = build(4, 4)
      mid = 4 → node = TreeNode(9)  ← 葉ノード
      return TreeNode(9)
    return TreeNode(5, left=None, right=TreeNode(9))

完成した BST:
         0          ← 根（配列の中央）
        / \
      -10    5
         \    \
         -3    9

高さ: 左=2, 右=2  差=0  ✅ 高さ平衡！

処理フローチャート

🗺️ フローチャートの読み方

楕円（緑）＝ 開始・終了
四角（青）＝ 処理ステップ
ひし形（黄）＝ 条件分岐
赤ボックス＝ 終端処理
緑矢印＝「いいえ」（処理続行） 赤矢印＝「はい」（早期終了） グレー矢印＝通常フロー
開始: build(lo, hi) lo > hi ? （空区間の確認） はい None を返す いいえ mid = (lo + hi) // 2 node = TreeNode(nums[mid]) node.left = build(lo, mid - 1) node.right = build(mid + 1, hi) return node 終了（サブツリーのルートを返した）

🔎 入力例 nums = [-10, -3, 0, 5, 9] でのフロー追跡

  1. 「開始」→ build(0, 4) が呼ばれる
  2. 「lo > hi?」→ 0 ≤ 4 なので「いいえ」の経路へ
  3. 「mid を計算」→ mid=2, node=TreeNode(0)
  4. 「左部分木」→ build(0,1) で同じフローを再帰実行し TreeNode(-10, right=TreeNode(-3)) を構築
  5. 「右部分木」→ build(3,4) で TreeNode(5, right=TreeNode(9)) を構築
  6. 「return node」→ 根 TreeNode(0) を返して終了

計算量分析

📖 Big-O 記法の読み方（入力サイズ n が大きくなるにつれて処理時間がどう増えるかの目安）

O(1)
常に一定
例：辞書の直接引き
O(log n)
入力の対数に比例
例：二分探索
O(n)
入力に比例
例：リストを1回走査
O(n²)
入力の2乗
例：二重ループ
計算量の種類 本実装（インデックス版） スライス版（比較）
時間計算量 O(n) O(n log n)
空間計算量（追加） O(log n) O(n log n)
スライスコピー なし ✅ あり（毎回コピー）❌
n=10,000 時の再帰深度 ≈ 14 段 ≈ 14 段

🔍 なぜこの計算量になるのか

時間計算量 O(n)：nums の各要素はちょうど1回だけ TreeNode(nums[mid]) として処理されます。n 個の要素なら n 回のノード生成が起こり、それ以外の処理（インデックス計算・代入）も O(1) なので全体 O(n) です。

空間計算量 O(log n)：スライスコピーを使わないため、追加メモリは再帰スタック（＝関数の呼び出し履歴を記録するメモリ）のみです。高さ平衡な木の高さは log₂(n) 程度なので、n=10,000 のとき再帰深度は最大 ⌈log₂(10000)⌉ = 14 段程度。Python のデフォルト再帰上限（1000回）に対して余裕があります。

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。

▶ O記法（Big-O 記法）
入力サイズ n が大きくなるにつれて処理時間・メモリがどう増えるかを表す記法。O(n) は「n に比例して増える」、O(log n) は「n が2倍になっても処理は1ステップ増えるだけ」を意味します。常数倍の差は無視して、最も支配的な項だけで表します。
▶ 二分探索木（BST）
Binary Search Tree の略。各ノードについて「左の子はすべて自分より小さく、右の子はすべて自分より大きい」という規則を持つ木構造です。この規則のおかげで、平衡が保たれていれば検索・挿入を O(log n) で行えます。
▶ 高さ平衡
木のどのノードについても、左の部分木と右の部分木の高さの差が 1 以下であること。平衡が崩れた BST は最悪 O(n)（一本道の竹のような形）になりますが、高さ平衡が保たれていれば O(log n) を維持できます。
▶ 再帰（recursion）
関数が自分自身を呼び出すこと。「同じ構造の小さな問題に分割できる」場面で有効です。マトリョーシカ人形のように、外側のフィギュアを開くと同じ形の小さいフィギュアが入っているイメージです。必ず「終了条件（ベースケース）」が必要で、これがないと無限ループになります。
▶ ベースケース（基底条件）
再帰を止める条件のこと。本問では lo > hi（有効な要素がない空区間）がベースケースで、None を返します。ベースケースは「これ以上小さく分割できない最小の問題」です。
▶ 分割統治法
大きな問題を「分割（Divide）」→ 小さな問題を「統治（Conquer）＝再帰で解く」→ 結果を「結合（Combine）」する手法。本問では「配列を左右に分割 → 各部分で再帰 → 左右の子ノードとして接続」がこのパターンに当たります。
▶ 床除算（//）
小数点以下を切り捨てる割り算。Python では // 演算子で表します。例：(0+4)//2 = 2、(0+3)//2 = 1。int((0+4)/2) と同じ結果ですが、CPython では // は C言語レベルの整数演算に最適化されており、型変換コストがありません。
▶ 再帰スタック
関数が自分を呼び出すたびに「どこに戻るか」の情報が積み上がるメモリ領域。本問では木の高さ（log n 程度）分だけ積み重なります。Python のデフォルト上限は 1000 段で、n=10,000 のとき本問の深さは最大 14 段なので余裕があります。
▶ スライスコピー
nums[lo:hi] のようにリストの一部を取り出す操作。Python では新しいリストオブジェクトがヒープ（動的メモリ領域）に生成されます。再帰のたびに呼ぶと O(n log n) のメモリが使われるため、本実装ではインデックス lo/hi を渡すことでこのコストを O(1) に抑えています。
▶ 葉ノード（leaf node）
左右両方の子が None のノード。木の末端を形成します。本問では1要素の区間（lo=hi）から作られるノードが葉ノードになります（左右の子がともに空区間として None を返す）。