再帰 DFS + 反復 BFS による O(n) 実装
💡 この問題を一言で言うと：「二分木の左右が完全に鏡写しかどうかを確認する問題」
「鏡写し」とは、木の中心軸（ルート）を境に、左サブツリーを裏返すと右サブツリーとぴったり重なる状態です。 単に「左右の値が同じ」だけでは不十分で、構造（形）と値の両方が対応していなければなりません。
⚠️ なぜ単純な方法では解けないのか
None（存在しない）の場合のケースを3パターン（両方None・片方None・両方あり）に分けて処理しないとバグになる
[2,2,2,null,2]）で誤検知しやすい
入力: [1, 2, 2, 3, 4, 4, 3]
出力: True
1
/ \
2 2
/ \ / \
3 4 4 3
理由: 左右が完全に鏡写し
左の左子(3) ↔ 右の右子(3) ✅
左の右子(4) ↔ 右の左子(4) ✅
入力: [1, 2, 2, null, 3, null, 3]
出力: False
1
/ \
2 2
\ \
3 3
理由: left.leftがnullである一方で
right.rightは3なので
nullと3が一致せず非対称になる ❌
各ステップをクリックすると詳細が表示されます。▶ Play で自動再生も可能です。
📋 このコードの構造（先に全体像を把握しよう）
isSymmetric：エントリーポイント。root が None なら即
True、そうでなければヘルパーへ
_is_mirror：2つのノードを受け取り、3ケース（両方None・片方None・両方あり）で鏡写し判定
isSymmetricIterative：deque を使う反復版（スタック深度制限を回避したい場合）
from collections import deque
# LeetCode が提供する TreeNode クラス（提出時はコメント済みのものを使用）
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
# =========================================================
# 解法①: 再帰版（メイン）
# =========================================================
def isSymmetric(self, root):
"""
二分木が鏡写し（対称）かどうかを再帰で判定する。
:type root: Optional[TreeNode]
:rtype: bool
Time: O(n) - 全ノードを1回ずつ訪問する
Space: O(h) - 再帰スタックの深さ（h = 木の高さ）
"""
# rootがNone（空の木）は「対称」と定義する
if root is None:
return True
# rootは中心軸なので比較しない。左子と右子を最初のペアとして渡す
return self._is_mirror(root.left, root.right)
def _is_mirror(self, left, right):
"""
2つのノードが「鏡写し」の関係かどうかを再帰的に確認するヘルパー。
:type left: Optional[TreeNode]
:type right: Optional[TreeNode]
:rtype: bool
"""
# ── 基底条件① ──
# 両方Noneなら「空同士」= 対称 → True
# 例: 葉ノードの子（存在しない位置）同士を比較した場合
if left is None and right is None:
return True
# ── 基底条件② ──
# 片方だけNoneなら「一方だけ枝がある」= 非対称 → False
# `is None` を使う: `== None` より高速（同一性チェック）
if left is None or right is None:
return False
# ── 再帰ステップ ──
# 3条件を `and` で繋ぐ。短絡評価で値が違えば即Falseを返す
return (
left.val == right.val # 条件1: 値が同じか？
and self._is_mirror(left.left, right.right) # 条件2: 外側ペア
and self._is_mirror(left.right, right.left) # 条件3: 内側ペア
)
# =========================================================
# 解法②: 反復版（フォローアップ）
# =========================================================
def isSymmetricIterative(self, root):
"""
二分木が鏡写しかどうかを反復（deque）で判定する。
RecursionError が心配な場合はこちらを使う。
deque を使う理由: list.pop(0) は O(n) だが
deque.popleft() は O(1) で高速。
:type root: Optional[TreeNode]
:rtype: bool
Time: O(n) Space: O(w) - wは木の最大幅
"""
if root is None:
return True
# dequeに「鏡ペア」をタプルで格納して順番に比較する
queue = deque()
queue.append((root.left, root.right))
while queue:
# FIFO（先入れ先出し）でペアを取り出す
left, right = queue.popleft()
if left is None and right is None:
continue # 両方None → OK、次のペアへ
if left is None or right is None:
return False # 片方だけNone → 非対称
if left.val != right.val:
return False # 値が違う → 非対称
# 次に確認すべき鏡ペアをキューに追加
queue.append((left.left, right.right)) # 外側ペア
queue.append((left.right, right.left)) # 内側ペア
return True
▶ 入力例
root = [1, 2, 2, 3, 4, 4, 3]
での動作トレース（再帰版）
isSymmetric(root=1)
→ root != None → _is_mirror(root.left=2, root.right=2)
_is_mirror(left=Node(2), right=Node(2))
→ 両方Noneでない、片方Noneでない
→ 2 == 2 ✅
→ _is_mirror(left.left=Node(3), right.right=Node(3)) ← 外側ペア
_is_mirror(left=Node(3), right=Node(3))
→ 3 == 3 ✅
→ _is_mirror(None, None) → True ✅
→ _is_mirror(None, None) → True ✅
→ True ✅
→ _is_mirror(left.right=Node(4), right.left=Node(4)) ← 内側ペア
_is_mirror(left=Node(4), right=Node(4))
→ 4 == 4 ✅
→ _is_mirror(None, None) → True ✅
→ _is_mirror(None, None) → True ✅
→ True ✅
最終結果: True and True and True = True ✅
▶ 入力例
root = [1, 2, 2, null, 3, null, 3]
での動作トレース（短絡評価の効果）
_is_mirror(left=Node(2), right=Node(2))
→ 2 == 2 ✅
→ _is_mirror(left.left=None, right.right=Node(3)) ← 外側ペア
_is_mirror(left=None, right=Node(3))
→ 片方だけ None → False ❌ ← ここで即終了！
→ False なので and の短絡評価が働き
内側ペアの _is_mirror は呼ばれない（省エネ！）
最終結果: False ❌
🗺️ フローチャートの読み方
この図は
_is_mirror(left, right)
ヘルパー関数の処理の流れを表しています。
上から下へ読み進め、ひし形の分岐で「はい/いいえ」のどちらかの経路を進みます。
🔎 入力例
[1, 2, 2, 3, 4, 4, 3]
でのフロー追跡
📖 Big-O 記法の読み方（入力サイズ n が大きくなるにつれて処理時間がどう増えるかの目安）
| 解法 | 時間計算量 | 空間計算量 | 最悪ケース（空間） |
|---|---|---|---|
| 再帰（DFS） | O(n) | O(h) | O(n)（一直線の木） |
| 反復（BFS with deque） | O(n) | O(w) | O(n)（完全二分木最下段） |
🔍 なぜこの計算量になるのか
時間計算量 O(n)：どちらの解法も、各ノードを最大1回ずつ訪問します。n個のノードがある木では、最大
n/2 ペアを比較するため O(n/2) = O(n) です。
空間計算量（再帰）O(h)：h
は木の高さです。再帰呼び出しは「コールスタック（＝関数の呼び出し履歴を記録するメモリ領域）」に積み重なります。最悪ケースの一直線の木では
h = n になるため O(n) です。バランスの取れた木では h = log n になります。
空間計算量（反復）O(w)：w は木の最大幅です。deque
には同じ深さのペアが格納されるため、完全二分木の最下段（= n/2
個のノード）が最悪ケースで O(n) になります。
⚡ 再帰 vs 反復：どちらを選ぶか
🌀 再帰版を選ぶ場面
🔁 反復版を選ぶ場面
このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。
popleft()
がO(1)で高速（list.pop(0)
はO(n)）。 C言語で実装されているため Pure Python より大幅に高速。
sys.getrecursionlimit()）。
A and B
でAが
False
なら、Bをまったく評価せず即座に
False
を返す仕組み。
この問題では値が違えば外側・内側ペアの再帰呼び出しが省略される。
非対称が早い段階で分かるほど効果が大きい最適化テクニック。
TreeNode
クラスで表現され、.val, .left,
.right
の3つの属性を持つ。
append()
で末尾追加、popleft()
で先頭取り出しにより実現する。
sys.setrecursionlimit(n)
で上限を変更可能。または反復版を使うことで根本的に回避できる。