BFS（幅優先探索）+ 偶奇反転で O(n) 実装
💡 一言で言うと：「二分木を階層ごとに、偶数階層は左→右・奇数階層は右→左と 交互にジグザグ で値を収集する問題」
💡 この問題を一言で言うと：「二分木を階層ごとに読み取り、1階層おきに読む向きを反転させる問題」
木の各階層（レベル）をキュー（待ち行列）で順番に処理し、偶数番目の階層は左→右、奇数番目の階層は右→左の順で値を収集します。 最終的に各階層の値リストを2次元配列として返します。
⚠️ なぜ単純な方法では解けないのか
level_size
を事前に固定するのが鍵です。
list
か
deque
か）がパフォーマンスに直結します。
例 1
階層0→[3]（左→右）、階層1→[20,9]（右→左に反転）、階層2→[15,7]（左→右）
例 2
ノードが1つだけなので、そのまま[[1]]を返す。
例 3
ガード節（root is None）で即座に空リストを返す。
📌 制約
root は
None
の場合あり（空ツリー）
📋 このコードの構造（先に全体像を把握しよう）
root is None
なら即
[] を返す
collections.deque
にルートノードを入れてキューを初期化する
while queue:
で階層ループ —
level_size
を固定してから内側ループへ
from __future__ import annotations
from typing import TYPE_CHECKING, Optional
from collections import deque
if TYPE_CHECKING:
class TreeNode:
val: int
left: Optional[TreeNode]
right: Optional[TreeNode]
def __init__(self, val=0, left=None, right=None) -> None: ...
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
# ── ガード節 ──────────────────────────────────────────────
# root が None（空ツリー）なら即座に空リストを返す。
# 後続処理で node.val へアクセスして AttributeError が起きるのを防ぐ。
if root is None:
return []
result: list[list[int]] = []
# ── deque（両端キュー）の初期化 ───────────────────────────
# list.pop(0) は O(n)、deque.popleft() は O(1)。
# 全ノード分繰り返すと list では O(n²) になってしまう。
queue: deque[TreeNode] = deque([root])
# ── BFS メインループ ──────────────────────────────────────
while queue:
# 「今の階層のノード数」をここで固定する。
# ループ中に子ノードをキューへ追加するため、固定しないと
# 今の階層と次の階層の境界が崩れてしまう。
level_size: int = len(queue)
level_values: list[int] = []
for _ in range(level_size):
# deque の先頭から O(1) で取り出す
node: TreeNode = queue.popleft()
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)
# ── ジグザグ処理（偶奇による方向切り替え）──────────────
# len(result) == 「完了済み階層数」 == 「現在の階層番号」
# 偶数（0,2,4…）→ 左→右（そのまま追加）
# 奇数（1,3,5…）→ 右→左（in-place で逆順にする）
# list.reverse() は新しいリストを作らない in-place 操作なので
# [::-1] よりメモリ効率・速度ともに優れる。
if len(result) % 2 == 1:
level_values.reverse()
result.append(level_values)
return result▶ 入力例 [3,9,20,null,null,15,7] での動作トレース
初期状態:
queue = deque([Node(3)])
result = []
─ 階層 0（len(result)=0 → 偶数 → そのまま）─────────────────
level_size = 1
popleft() → Node(3) → level_values = [3]
└ Node(9) と Node(20) をキューへ追加
0 % 2 == 0 → reverse しない
result = [[3]] queue = deque([Node(9), Node(20)])
─ 階層 1（len(result)=1 → 奇数 → 逆順）──────────────────────
level_size = 2
popleft() → Node(9) → level_values = [9] （子なし）
popleft() → Node(20) → level_values = [9, 20]
└ Node(15) と Node(7) をキューへ追加
1 % 2 == 1 → reverse() → level_values = [20, 9]
result = [[3],[20,9]] queue = deque([Node(15), Node(7)])
─ 階層 2（len(result)=2 → 偶数 → そのまま）─────────────────
level_size = 2
popleft() → Node(15) → level_values = [15] （子なし）
popleft() → Node(7) → level_values = [15, 7] （子なし）
2 % 2 == 0 → reverse しない
result = [[3],[20,9],[15,7]] queue = deque([]) ← 空
while queue: → False → ループ終了
最終出力: [[3], [20, 9], [15, 7]] ✅
🗺️ フローチャートの読み方
🔎 入力例 [3,9,20,null,null,15,7] でのフロー追跡
return [[3],[20,9],[15,7]]
✅
📖 Big-O 記法の読み方（入力サイズ n が大きくなるにつれて処理時間がどう増えるかの目安）
| 種別 | 計算量 | 理由 |
|---|---|---|
| 時間計算量 | O(n) |
全ノードを一度だけ訪問する。reverse()
は各階層サイズ k に対して O(k) だが、全階層を合計すると O(n)
|
| 空間計算量 | O(n) | deque は最大で最も幅の広い階層のノード数を格納する。完全二分木では最大 n/2 ノード。result リストも最終的に n ノード分を格納する |
| 操作 | コード | 追加メモリ | 速度 |
|---|---|---|---|
| ✅ in-place（採用） | level.reverse() | O(1)（なし） | 高速（C実装） |
| ❌ Pure（不採用） | level[::-1] | O(k)（新リスト生成） | やや低速 |
🔍 なぜこの計算量になるのか
BFS
では各ノードをキューから1回だけ取り出し、その値を収集して子ノードを追加します。
ノード数を n とすると、popleft・append・level_values.append はすべて O(1)
なので合計 O(n)。
reverse()
は各階層のサイズ k に対して O(k) ですが、
すべての階層のサイズの合計はちょうど n になるため、全体でも O(n)
に収まります。 空間については、deque
に同時に入るノードは「最も幅の広い階層」だけなので最大 O(n/2) = O(n) です。
このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。
collections.deque
が提供するデータ構造。先頭・末尾への追加・取り出しがどちらも
O(1)（一定時間）で行える。list で
pop(0)（先頭取り出し）をすると O(n) かかるため、BFS キューには必ず deque
を使う。
return
する書き方。if root is None: return []
がそれにあたる。
list.reverse()
がその代表例。list[::-1]
は新しいリストを生成する（Pure 操作）。in-place
の方が追加メモリを消費しない分、効率的。
level_size
の固定がこれを保証する。