アルゴリズム概要

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

「木の同じ深さ（階層）にあるノードを全部集めて1つのリストにまとめ、それを深さ順に並べた2次元配列を返す問題」です。
左から右の順番でノードを集める必要があります。

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

  • 「縦方向（深さ優先）」に探索するだけでは、同じ深さのノードをまとめる境界が分からない
  • list.pop(0) を使うと先頭削除が O(n) になり全体が O(n²) へ悪化する
  • ノードの値が 0 のとき、or トリックは 0（falsy）と誤判定して壊れる
O(n)
時間計算量
O(n)
空間計算量
deque
データ構造
BFS
探索手法

📥 入出力例

入力（ツリー）

    3
   / \
  9  20
     / \
    15   7

出力と理由

[[3],[9,20],[15,7]]

深さ0 → [3]
深さ1 → [9, 20]  ← 左から右
深さ2 → [15, 7]  ← 左から右

📋 制約

  • ノード数：0 以上 2000 以下
  • ノードの値：-1000 以上 1000 以下（0 が含まれる）

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

各ステップをクリックするか、▶ Play ボタンで自動再生できます。

Python 実装

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

  1. 空ツリーのチェック：root が None なら即座に [] を返す
  2. deque の初期化：root をキューに入れて BFS 開始の準備
  3. while ループ：キューが空になるまで、階層ごとに処理する
  4. level_size の固定：今の階のサイズをここで確定させる（核心）
  5. for ループ：level_size 個だけ popleft() し、値収集と子の登録を行う
  6. 結果への追加：今の階の値リストを result に追加する
from collections import deque
from typing import Optional


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        # 基底条件: root が None（空ツリー）なら即座に空リストを返す
        # None チェックをしないと後続の node.val アクセスでクラッシュする
        if root is None:
            return []

        result: list[list[int]] = []

        # collections.deque をキューとして使う
        # list.pop(0) は O(n) だが deque.popleft() は O(1)
        # deque は C言語実装の双方向キューで先頭・末尾への操作が高速
        queue: deque[TreeNode] = deque([root])

        # キューが空になるまでループ（= 全ノードを処理し終えるまで）
        while queue:
            # ── BFS の核心：今の階のサイズをここで固定する ──
            # ループ中に popleft()/append() で queue の長さが変化するため
            # 先に変数へ保存しないと「今の階」の範囲がずれて Wrong Answer になる
            level_size: int = len(queue)
            level_values: list[int] = []

            for _ in range(level_size):
                # popleft() でキューの先頭ノードを O(1) で取り出す
                node: TreeNode = queue.popleft()

                # val を直接 append する（0 も正しく追加される）
                # `or` トリックは val=0 のとき falsy と判定されて壊れるため使わない
                level_values.append(node.val)

                # 子が存在する場合のみキューへ追加（次の階の準備）
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            result.append(level_values)

        return result

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

初期状態: queue = deque([Node(3)]),  result = []

━━ ループ 1回目（深さ0） ━━
  level_size = 1   ← ここで固定！
  vals = []
  i=0: popleft() → Node(3)   queue = deque([])
       append(3)  → vals = [3]
       left=Node(9)  → queue = deque([Node(9)])
       right=Node(20) → queue = deque([Node(9), Node(20)])
  result = [[3]]

━━ ループ 2回目（深さ1） ━━
  level_size = 2   ← ここで固定！
  i=0: Node(9)  → vals=[9]       子なし
  i=1: Node(20) → vals=[9,20]    left=Node(15), right=Node(7)
  result = [[3], [9, 20]]

━━ ループ 3回目（深さ2） ━━
  level_size = 2
  i=0: Node(15) → vals=[15]      子なし
  i=1: Node(7)  → vals=[15,7]    子なし
  result = [[3], [9, 20], [15, 7]]

queue が空 → ループ終了
戻り値: [[3], [9, 20], [15, 7]] ✅

処理フローチャート

🗺️ フローチャートの読み方（Mermaid 記法）

([…]) スタジアム形（緑）
= 開始・終了
[…] 四角形（青）
= 処理ステップ
{…} ひし形（黄）
= 条件分岐
Yes（はい） No（いいえ）
読み込み中…
緑 = 開始・終了ノード 青 = 通常の処理 黄 = 条件分岐 紫 = BFS の核心処理

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

  1. 「Start」 → root=Node(3) を受け取る
  2. 「root is None?」 → いいえ → 初期化: result=[], queue=deque([Node(3)])
  3. 「queue は空?」 → いいえ（Node(3) がある）→ level_size=1, vals=[]
  4. 「i < 1?」 → はい → popleft()=Node(3), vals=[3], left=Node(9)→追加, right=Node(20)→追加
  5. 「i < 1?」 → いいえ → result.append([3]) → ループバック
  6. （深さ1）level_size=2, Node(9)→vals=[9], Node(20)→vals=[9,20], Node(15)&Node(7)追加
  7. （深さ2）level_size=2, Node(15)→vals=[15], Node(7)→vals=[15,7]
  8. 「queue は空?」 → はい → 「return result」へ → [[3],[9,20],[15,7]] ✅

計算量分析

📖 Big-O 記法の読み方（n = ノード数）

O(1)
常に一定
例：辞書の直接引き
O(n)
入力に比例
例：リストを1回走査
O(n²)
入力の2乗
例：二重ループ総当たり
list.pop(0)
先頭削除は O(n)
全体 O(n²) になる
種別 計算量 理由
時間計算量 O(n) 各ノードを popleft() で1回だけ処理（O(1)×n回）
空間計算量 O(n) キューに最大で最下層のノード数（最大 n/2 個）が入る
比較：list.pop(0) O(n²) 先頭削除のたびに残り全要素をシフト（O(n)×n回）

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

全ノード数を n とすると、各ノードはキューへの append()（O(1)）と popleft()（O(1)）を1回ずつ行うため、 合計操作回数は 2n = O(n) です。 空間については、完全二分木の最下層に最大 n/2 個のノードが集まるため、 キューの最大サイズは O(n) となります。 これは出力配列 result のサイズも同様で、全ノードの値を格納するため O(n) です。

📖 用語集

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

▶ BFS（幅優先探索）
Breadth-First Search の略。グラフや木を「横方向に広がりながら」探索する方法。 同じ深さのノードをすべて処理してから次の深さへ進む。 「エレベーターで同じ階を全部回ってから次の階へ行く」イメージ。 この問題では「同じ階層のノードをまとめる」処理と自然に一致するため選ばれる。
▶ Big-O 記法
アルゴリズムの「入力サイズが大きくなるにつれて処理時間やメモリがどう増えるか」を表す記法。 O(1) は常に一定、O(n) は入力に比例、O(n²) は入力の2乗で増加する。 実際の秒数ではなく「増え方の傾向」を表す。
▶ deque（デック）
collections.deque のこと。 Doubly-Ended Queue（両端キュー）の略。前からも後ろからも O(1) で出し入れできる「両端開きの箱」。 Python の list の先頭削除は O(n) だが、 deque の popleft() は O(1)。 C言語で実装されており高速。
▶ falsy（フォールシー）
Python の if の条件式で False 相当と見なされる値。 0、None、[]、"" などが該当する。 ノードの値 val = 0 は falsy なので、 0 or 式 という書き方は「0のとき右辺を実行する」という誤動作を引き起こす。
▶ FIFO（先入れ先出し）
First In, First Out の略。最初に入れたものを最初に取り出す順序。 銀行の窓口の行列と同じ仕組み。キューはこの性質を持つ。 BFS はこの性質を利用して「深さが浅いノードから順番に処理する」を実現する。
▶ キュー（Queue）
先に入れたものを先に取り出す（FIFO）データ構造。 銀行の窓口の行列と同じ。 BFS では「処理待ちのノード」をキューに積み、先頭から順番に処理することで 「浅い順」に探索できる。
▶ level_size（階層サイズの固定）
BFS の while ループの各反復の開始時に level_size = len(queue) で 「今の階のノード数」を変数に保存するテクニック。 ループ中に子の追加で queue の長さが変化するため、先に固定しないと 「今の階」と「次の階」の境界が混在して Wrong Answer になる。
▶ 二分木（Binary Tree）
各ノードが「左の子」と「右の子」の最大2つを持つ木構造のデータ。 木の頂点を「根（root）」と呼び、子を持たないノードを「葉（leaf）」と呼ぶ。 根からあるノードまでの辺の数を「深さ（depth）」と呼ぶ。根の深さは 0。
▶ popleft()
deque の先頭要素を O(1) で取り出すメソッド。 list.pop(0) は残り全要素を前にシフトするため O(n) かかるが、 deque.popleft() は双方向連結リストの先頭ポインタを1つ進めるだけなので O(1)。 n=2000 のとき、この差は 2000 回 vs 最大 4,000,000 回の操作差になる。