再帰DFS（深さ優先探索）による O(n) 実装
💡 一言で言うと：「2本の二分木が形も値もまったく同じかどうかを確認する問題」
💡 この問題を一言で言うと：「2本の二分木が、形も値もまったく同じかどうかを確認する問題」
二分木（＝各ノードが左と右に高々1つずつ子を持つ木構造）が2本与えられます。 「同じ木」とは、すべての対応するノードが同じ値を持ち、かつ木の形（どこに子がいるか）も完全に一致することです。 単純に見えますが、「木の形の比較」という点で少し考える必要があります。
⚠️ なぜ単純な方法では解けないのか
例1 → true
p: [1,2,3] q: [1,2,3]
1 1
/ \ / \
2 3 2 3
形も値もすべて同じ → true ✅
例2 → false
p: [1,2] q: [1,null,2]
1 1
/ \
2 2
値は同じでも位置（左 vs 右）が違う → false ❌
例3 → false
p: [1,2,1] q: [1,1,2]
1 1
/ \ / \
2 1 1 2
左右の値が入れ替わっている → false ❌
📌 制約
0 以上
100 以下
-10⁴ ≤ Node.val ≤ 10⁴
再帰DFSがどのように動くかを4つのステップで確認しましょう。 ▶ Play ボタンで自動的に進めることもできます。
📋 このコードの構造（先に全体像を把握しよう）
None
かを確認 → 同じ葉の先端なら
True
None
かを確認 → 構造が違うので
False
p.val != q.val）が違うなら
False
True
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: Optional[TreeNode]
:type q: Optional[TreeNode]
:rtype: bool
"""
# ── ① 両方 None のとき ──────────────────────────
# 葉ノードのさらに下（何もない場所）に両方とも到達した。
# 「どちらにも子がない」＝構造が一致している → True
# `is None` を使うのが Pythonic（Pythonらしい慣用的な書き方）
if p is None and q is None:
return True
# ── ② 片方だけ None のとき ──────────────────────
# ①で「両方 None」はすでに return 済み。
# ここに来るのは「どちらか一方だけ None」の場合のみ。
# 片方にノードがあり、片方にない = 構造が違う → False
if p is None or q is None:
return False
# ── ③ 値の比較 ───────────────────────────────────
# ①②を通過した時点で p も q も None でないことが確定。
# pylance もここでは p・q を TreeNode として認識する
# （型の絞り込み = Type Narrowing と呼ばれる仕組み）。
if p.val != q.val:
return False
# ── ④ 左右の子木を再帰で比較 ────────────────────
# 根の値が一致したので、次は左・右の子木を同じ手順で比較する。
# `and` の短絡評価（左が False なら右は実行しない）で
# 不一致が見つかった時点で即座に False を返せる。
return (
self.isSameTree(p.left, q.left)
and self.isSameTree(p.right, q.right)
)▶ 入力例 p=[1,2] / q=[1,null,2] での動作トレース
呼び出し①: isSameTree(Node(1), Node(1)) → ① 両方非 None → パス → ② どちらも非 None → パス → ③ 1 == 1 → パス（値が等しいので続ける） → ④ 左の子を比較するために再帰呼び出し 呼び出し②: isSameTree(Node(2), None) ← p.left=Node(2), q.left=None → ① p は非 None → パス（両方 None ではない） → ② p は非 None だが q は None → return False ← ここで終了！ 呼び出し①に戻る: → isSameTree(p.left, q.left) = False → and の短絡評価：False and ... → 右辺の再帰は実行されない → return False 最終結果: False ✅
🗺️ フローチャートの読み方
🔎 入力例 p=[1,2,3] / q=[1,2,3] でのフロー追跡
📖 Big-O 記法の読み方（入力サイズが大きくなるにつれて処理時間がどう増えるかの目安）
| 観点 | 計算量 | 条件 |
|---|---|---|
| 時間計算量 | O(n) | n = 2つの木の総ノード数。全ノードを最大1回訪問 |
| 空間計算量（平均） | O(log n) | 平衡二分木の場合（高さ h ≈ log₂ n） |
| 空間計算量（最悪） | O(n) | 一本道の木（高さ = ノード数）の場合 |
| 本問題での実際 | O(100) | ノード数 ≤ 100 の制約により事実上定数 |
🔍 なぜこの計算量になるのか
時間計算量 O(n)：「2つの木が同じかどうか」を確認するには、すべてのノードを少なくとも1回は調べなければなりません。再帰DFSは各ノードをちょうど1回だけ訪問するため、n
ノードに対して O(n) の操作で済みます。
空間計算量 O(h)：再帰呼び出しはコールスタック（＝関数呼び出しの積み重ね）にメモリを使います。一番深くまで潜ったとき（葉ノードに到達したとき）の積み重ねの深さが木の高さ
h なので、O(h)
のメモリが必要です。追加のデータ構造（リストやキューなど）は一切使わないため、スタック以外のメモリは
O(1) です。
📊 アプローチ別比較
| アプローチ | 時間 | 空間 | 特徴 |
|---|---|---|---|
| ✅ 再帰DFS（採用） | O(n) | O(h) | コードが最もシンプル。問題の定義と1対1対応 |
| 反復DFS（スタック） | O(n) | O(h) | list をスタック代わりに使用。再帰を使わない |
| 反復BFS（キュー） | O(n) | O(n) | deque 使用。常に O(n) メモリを消費して不利 |
このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。
null
に相当します。 二分木では、子がいないノードの
left や
right
が
None
になります。 比較する際は
== None
ではなく
is None
を使うのが Pythonic です。
p is None and q is None
のときに
True
を返す部分です。
A and B
の A が
False
なら B を評価しない・
A or B
の A が
True
なら B を評価しない仕組み。 今回のコードでは
isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
において、
左の子木が一致しなければ右の再帰は実行されません。不必要な処理を省いて効率化できます。
TreeNode
クラスはこの構造を
left と
right
の2つの参照で表現しています。
x == None
より
x is None、
len(lst) == 0
より
not lst
が Pythonic とされています。