アルゴリズム概要

💡 この問題を一言で言うと：「根ノードから最も近い葉ノードまでの最短経路のノード数を返す問題」

「最小深さ」とは、木の根（一番上）から出発して、最初に到達できる葉（子を持たないノード）までのノード数のことです。深さは根を1として数えます。葉ノードとは、左の子も右の子もどちらも存在しないノードのことです。

⚠️ なぜ単純な方法では解けないのか

  • 「片側だけに子があるノード」が罠になる：左の子がない＝葉、ではありません。たとえば右の子だけを持つノードは葉ではなく、右へ続く経路がある「中間ノード」です。例2（[2,null,3,null,4,null,5,null,6]）がその典型で、最小深さはなんと 5 になります。
  • DFS（深さ優先）では最短を保証できない：DFS は「葉に到達するまで一方向に潜り続ける」性質があるため、偶然最初に見つかった葉が最短とは限りません。BFS なら浅いノードから順番に調べるので、最初に見つかった葉が必ず最短です。
O(n)
時間計算量
O(w)
空間計算量 (w=最大幅)
BFS
アルゴリズム
deque
使用データ構造

例1: 通常の二分木

入力: root = [3,9,20,null,null,15,7]

      3
     / \
    9  20
       / \
      15   7

出力: 2

根(3)→左の子(9) の経路が長さ2で最短。ノード9は左も右も子がない「葉」のため、深さ2が答えになります。

例2: 一方向にだけ伸びる木 

入力: root = [2,null,3,null,4,null,5,null,6]

2
 \
  3
   \
    4
     \
      5
       \
        6   ← 唯一の葉

出力: 5

右方向にのみ子があり、唯一の葉はノード6。葉までの距離が5なのでその深さが答えです。

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

Python 実装

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

  1. エッジケース処理：root が None（空の木）なら即座に 0 を返す
  2. BFS キューを初期化：deque に (根ノード, 深さ=1) のペアを入れる
  3. キューが空になるまで繰り返す：浅い順にノードを一つずつ処理する
  4. 葉ノードに到達したら深さを返す（BFS の特性で、最初の葉が必ず最短経路） 
from typing import Optional
from collections import deque


class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        # ─────────────────────────────────────
        # エッジケース: 空の木 → 深さ 0 を返す
        # 根がなければ「葉までの道」自体が存在しない
        # ─────────────────────────────────────
        if root is None:
            return 0

        # ─────────────────────────────────────
        # BFS キューを初期化する
        # deque の popleft() は O(1) ← list より効率的
        # タプル (ノード, 現在の深さ) でペアを管理する
        # ─────────────────────────────────────
        queue: deque = deque()
        queue.append((root, 1))   # 根ノードは深さ 1 からスタート

        while queue:
            # popleft() = FIFO（先入れ先出し）→ 浅い順に処理
            node, depth = queue.popleft()

            # ─────────────────────────────────
            # 葉ノード判定: 左も右も子がない = 葉
            # BFS は浅い順なので、最初の葉 = 最小深さ
            # ─────────────────────────────────
            if node.left is None and node.right is None:
                return depth      # 最小深さ確定！

            # 子ノードは存在する場合のみキューに追加
            if node.left is not None:
                queue.append((node.left,  depth + 1))
            if node.right is not None:
                queue.append((node.right, depth + 1))

        return 0  # 有効な木なら通常ここに到達しない

▶ 入力例 [3,9,20,null,null,15,7] での動作トレース 

初期状態: queue = [(node=3, depth=1)]

反復 1: pop → (node=3, depth=1)
   左の子: 9 あり, 右の子: 20 あり → 葉ではない
   → queue に (node=9, depth=2) と (node=20, depth=2) を追加
   → queue = [(node=9, depth=2), (node=20, depth=2)]

反復 2: pop → (node=9, depth=2)
   左の子: None, 右の子: None → 🌿 葉ノード発見！
   → return 2   ✅ 答え: 2（探索終了）

※ node=20 はキューに残ったままですが、葉を見つけた時点で即 return
   するためこれ以上処理は行われません。

処理フローチャート

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

楕円（緑）＝ 開始・終了
四角（青）＝ 処理ステップ
ひし形（黄）＝ 条件分岐
緑＝はい 赤＝いいえ
開始 root is None ? （木が空かどうか） はい 0 を返す return 0 いいえ BFS キューを初期化 queue = deque([(root, 1)]) キューからノードを取り出す node, depth = queue.popleft() 葉ノード? left==None and right==None はい depth を返す return depth いいえ 子ノードをキューに追加 queue.append((child, depth + 1)) ル ー プ 終了

🔎 入力例 [3,9,20,null,null,15,7] でのフロー追跡

  1. 「開始」→ root = TreeNode(3) なので None ではない → 「いいえ」の経路へ
  2. 「BFS キュー初期化」→ queue = [(node=3, depth=1)] にセット
  3. 「キューから取出し」→ node=3, depth=1 を popleft で取り出す
  4. 「葉ノード?」→ node=3 の left=9, right=20 があるので「いいえ」→ 子をキューに追加
  5. 「子をキューに追加」→ queue = [(node=9, depth=2), (node=20, depth=2)] になりループ
  6. 「キューから取出し」→ node=9, depth=2 を取り出す
  7. 「葉ノード?」→ node=9 の left=None, right=None → 「はい」→ depth=2 を返す
  8. 「終了」→ 答え 2 を返して処理完了

フローの要点：
BFS はキューを使って「浅いノードから順番に」処理します。ループ（紫の矢印）は次のノードを処理するためにキューへ戻ることを表しています。右側の緑の線（サイドライン）は「条件を満たしたので早期リターン」する経路です。root is None のときは 0 を、葉ノードを見つけたときはそのときの depth を即座に返します。

計算量分析

📖 Big-O 記法の読み方（入力サイズ n が大きくなると処理時間がどう変わるか）

O(1)
常に一定
例：辞書の直接引き
O(n)
入力に比例
例：リストを1回走査
O(n log n)
n より少し多い
例：マージソート
O(n²)
入力の2乗
例：二重ループ総当たり
種別 記法 変数の意味 ケース
時間計算量 O(n) n = 木のノード総数 最悪ケース（全ノード訪問）
空間計算量 O(w) w = 木の最大幅（1段のノード最大数） 完全二分木では O(n/2) ≈ O(n)

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

時間 O(n)：最悪のケースでは、葉が最後の1個で木の最深部にある状況です（例2のような一方向に伸びる木）。この場合、全 n ノードをキューから1回ずつ取り出して処理するため、処理回数は n に比例します。ただし最良のケースは根ノード自体が葉（n=1）のときで、即座に O(1) で返ります。

空間 O(w)：キューには「同じ深さのノード」が同時に蓄積されます。最もノードが密集する段（= 木の最大幅 w）のとき、キューのサイズが最大になります。完全二分木の最下段では w ≈ n/2 となり、事実上 O(n) と等価です。

📖 用語集

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

▶ BFS（幅優先探索）
Breadth-First Search の略。木やグラフを「根に近い順」「浅い階層から順番に」探索するアルゴリズムです。「うずまきのように外側から内側に向かって広がる」イメージに例えられます。キュー（待ち行列）を使って実装し、最短経路の発見に特に適しています。対義語は DFS（深さ優先探索）。
▶ deque（デク）
double-ended queue（両端キュー）の略。Python の collections.deque が提供します。先頭と末尾の両端から O(1) の定数時間で要素の追加・取り出しができます。通常の list の pop(0) は O(n) のコストがかかるため、BFS には deque の使用が必須です。
▶ 葉ノード（リーフノード）
左の子も右の子も持たないノードのことです。木の末端に位置します。「葉」という名前は、木の葉っぱが枝の末端にあることに由来します。判定条件は node.left is None and node.right is None です。注意点：左右どちらか一方の子しか持たないノードは葉ではありません。
▶ キュー（待ち行列）/ FIFO
FIFO（First In, First Out = 先入れ先出し）の原則に従うデータ構造です。コンビニのレジ待ちの列と同じで、先に並んだ人が先に処理されます。BFS では「浅いノードを先に処理する」ために必須です。append() で末尾に追加し、popleft() で先頭から取り出します。
▶ 根ノード（ルートノード）
木の最上位に位置する唯一のノードです。親ノードを持ちません。木の探索はここから開始します。深さの数え方では、根ノードの深さを 1 として数えます（問題によっては 0 から数えることもあります）。
▶ 時間計算量 / 空間計算量
時間計算量：入力サイズ n が増えたときに、処理ステップ数がどのくらい増えるかの指標です。O(n) は「n が2倍になると処理も約2倍」を意味します。
空間計算量：アルゴリズムが使用するメモリ（RAM）の量の指標です。O(w) はキューに同時に蓄積されるノード数（= 木の最大幅 w）に比例することを示しています。
▶ 二分木（バイナリーツリー）
各ノードが最大2つの子（左の子・右の子）を持つ木構造のデータ構造です。「二分」とは「2つに分かれる」という意味で、各ノードで枝が最大2本に分岐します。LeetCode では TreeNode クラスが使われ、val（値）・left（左の子）・right（右の子）の3つの属性を持ちます。