アルゴリズム概要

💡 この問題を一言で言うと：「根から葉まで下りるルートの数値の合計が targetSum と一致するパスが1本でも存在するか？」を判定する問題です。

木（ツリー）は配列と違い、インデックスで直接アクセスできません。根から分岐を辿りながら合計を積み上げ、葉（末端）に到達した瞬間に目標値と比較する必要があります。

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

  • 木には「インデックス」がないため、すべてのパスを順番に辿って確認するしかありません。
  • 「葉の定義」（左右両方の子が None）を正確に判定しないと、木の途中のノードで誤って答えを確定してしまいます。
  • 値が負の場合もあるため、「合計が targetSum を超えたら打ち切り」などの最適化が使えません。
O(n)
時間計算量
O(h)
空間計算量
再帰DFS
アルゴリズム
0〜5000
ノード数制約

入出力例

Example 1
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22
✅ true
5→4→11→2 の合計が 22 になるから
Example 2
root = [1,2,3]
targetSum = 5
❌ false
1→2=3、1→3=4 どちらも5にならないから
Example 3
root = []
targetSum = 0
❌ false
木が空なのでパス自体が存在しないから

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

例：root = [5,4,8,11,null,13,4,7,2,...], targetSum = 22 を使って解説します。

Python 実装

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

  1. root が None かを確認する（空の木 or 葉を超えた場合）→ False を返す
  2. targetSum から現在のノードの値を引いて「残り目標値」を計算する
  3. 葉（左右の子が両方 None）に到達したら、残り目標値が 0 かどうかで答えを確定する
  4. 葉でなければ左・右の子に対して同じ処理を再帰的に呼び出し、どちらかが True なら True を返す

競技プログラミング版（再帰DFS） 

# LeetCode 112 – Path Sum（競技版：再帰DFS）
# Time: O(n)  Space: O(h)   n=ノード数, h=木の高さ

class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: bool
        """
        # ベースケース①: root が None = 空の木 or 葉を超えた
        # パスが存在しないので即 False を返す
        if root is None:
            return False

        # 現在ノードの値を targetSum から引く
        # 「残りあとどれだけ合計が必要か」を次の階層に引き継ぐ
        # 例) targetSum=22, root.val=5 → 次は 17 を目標にする
        targetSum -= root.val

        # ベースケース②: 葉（左右両方の子が None）に到達した
        # パスの終点なので、残り目標値がちょうど 0 か確認する
        if root.left is None and root.right is None:
            return targetSum == 0

        # 再帰ステップ: 左または右の子ツリーで条件を満たすパスがあれば True
        # 「or」は短絡評価: 左が True なら右を評価せずに即 True を返す
        return (self.hasPathSum(root.left, targetSum) or
                self.hasPathSum(root.right, targetSum))

▶ 入力例 root=[5,4,8,11,null,13,4,7,2,...], targetSum=22 での動作トレース 

hasPathSum(Node(5),  22) → targetSum = 22-5  = 17  → 葉でない → 左へ
  hasPathSum(Node(4),  17) → targetSum = 17-4  = 13  → 葉でない → 左へ
    hasPathSum(Node(11), 13) → targetSum = 13-11 =  2  → 葉でない → 左へ
      hasPathSum(Node(7),   2) → targetSum =  2-7  = -5  → 葉！→ -5==0? → False ❌
      hasPathSum(Node(2),   2) → targetSum =  2-2  =  0  → 葉！→  0==0? → True  ✅
    ← True が伝播
  ← True が伝播
← True が伝播

最終出力: True（パス 5→4→11→2, 合計=22）

業務開発版（反復DFS + deque）

⚠️ Python のデフォルト再帰制限は約 1000 です。5000ノードの一直線の木では超過する可能性があります。業務版は deque を使って再帰なしで安全に実装します。 
from collections import deque

class Solution:
    def hasPathSum(self, root, targetSum):
        if root is None:
            return False

        stack = deque([(root, targetSum)])

        while stack:
            node, remaining = stack.pop()
            remaining -= node.val

            if node.left is None and node.right is None:
                if remaining == 0:
                    return True
                continue

            if node.right is not None:
                stack.append((node.right, remaining))
            if node.left is not None:
                stack.append((node.left, remaining))

        return False

処理フローチャート

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

楕円 楕円（緑/赤）＝ 開始・終了
四角 四角（青）＝ 処理ステップ
ひし形 ひし形（黄）＝ 条件分岐
再帰 二重縦線（紫）＝ 再帰呼び出し
緑矢印＝はい / 成功 赤矢印＝いいえ / False 紫矢印＝再帰

✅ return False の出口は1か所に統合しています（② and ⑤ の両方が合流）

✅ 「はい」「いいえ」ラベルは分岐点の直隣に配置し、視線移動を最小化しています

✅ 再帰呼び出し⑥⑦ は二重縦線ボックスで通常の処理と区別しています 

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13.5px', 'lineColor': '#64748b', 'primaryBorderColor': '#2563eb', 'tertiaryColor': '#ede9fe'}}}%%
flowchart TD
    A(["① 開始\nhasPathSum( root, targetSum )"]):::start
    A --> B{"② root is None?\n空の木・存在しない子"}:::cond
    B -- "はい" --> F(["return False ❌\n【共通の False 出口】\n② と ⑤ の両方がここへ合流"]):::falseNode
    B -- "いいえ" --> C["③ remaining = targetSum − root.val\n例: 22 − 5 = 17"]:::proc
    C --> D{"④ 葉ノードか?\nleft is None  かつ  right is None"}:::cond
    D -- "はい（葉に到達）" --> E{"⑤ remaining == 0?\n合計がぴったり一致したか"}:::cond
    E -- "はい" --> T(["return True ✅\nパスが見つかった！"]):::trueNode
    E -- "いいえ" --> F
    D -- "いいえ（葉でない）" --> G[["⑥ hasPathSum( root.left,  remaining )\n左の子ツリーへ再帰\nTrue なら即 True（短絡評価 or）"]]:::rec
    G --> H[["⑦ hasPathSum( root.right, remaining )\n右の子ツリーへ再帰\nleft or right の結果を返す"]]:::rec
    H --> R(["⑧ 結果を上の階層へ返す\nleft_result  or  right_result"]):::result

    classDef start    fill:#d1fae5,stroke:#059669,stroke-width:2.5px,color:#065f46,font-weight:bold
    classDef cond     fill:#fef9c3,stroke:#ca8a04,stroke-width:2px,color:#78350f
    classDef proc     fill:#dbeafe,stroke:#2563eb,stroke-width:2px,color:#1e3a8a
    classDef falseNode fill:#fee2e2,stroke:#dc2626,stroke-width:2.5px,color:#7f1d1d,font-weight:bold
    classDef trueNode  fill:#dcfce7,stroke:#16a34a,stroke-width:2.5px,color:#14532d,font-weight:bold
    classDef rec      fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#3b0764
    classDef result   fill:#f1f5f9,stroke:#64748b,stroke-width:2px,color:#1e293b

    linkStyle 1 stroke:#dc2626,stroke-width:2.5px,color:#dc2626
    linkStyle 2 stroke:#16a34a,stroke-width:2px
    linkStyle 4 stroke:#16a34a,stroke-width:2px
    linkStyle 5 stroke:#16a34a,stroke-width:2.5px
    linkStyle 6 stroke:#dc2626,stroke-width:2.5px
    linkStyle 7 stroke:#7c3aed,stroke-width:2px
    linkStyle 8 stroke:#7c3aed,stroke-width:2px
    linkStyle 9 stroke:#64748b,stroke-width:2px

🔎 入力例 root=[5,4,8,11,null,13,4,7,2,...], targetSum=22 でのフロー追跡

  1. 「① 開始」→ root=Node(5), targetSum=22 を受け取る
  2. 「② root is None?」→ Node(5) ≠ None → いいえ（緑矢印で③へ）
  3. 「③ remaining 計算」→ remaining = 22 − 5 = 17
  4. 「④ 葉?」→ left=Node(4), right=Node(8) → いいえ（葉でない）→ 紫矢印で⑥へ
  5. 「⑥ 左再帰」→ hasPathSum(Node(4), 17) → … → hasPathSum(Node(2), 2) へ深潜り
  6. 「④ 葉?」→ Node(2) は葉 → はい → 「⑤ remaining==0?」→ 2−2=0 → はい → ✅ return True
  7. True が ⑥ or ⑦ を通じて上の階層へ次々と伝播 → 最終的に True を返す

🔴 return False の2つの経路について

② → False：root が None（空の木・存在しない子ノードを辿った）場合。パス自体が存在しない。
⑤ → False：葉に到達したが残り目標値が 0 でない場合。このパスの合計は targetSum と一致しない。
両経路とも「このパスに答えはない」という同じ意味を持つため、図では1つの出口ノードに合流させています。

計算量分析

📖 Big-O 記法の読み方

O(1)
常に一定
例：辞書の直接引き
O(n)
入力に比例
例：リストを1回走査
O(log n)
対数的に増加
例：均衡木の高さ
O(n²)
入力の2乗
例：二重ループ
項目 競技版（再帰） 業務版（反復deque）
時間計算量 O(n) O(n)
空間計算量 O(h) O(h)
均衡木の空間 O(log n) O(log n)
最悪（一直線） O(n) ⚠️再帰制限 O(n) ✅安全
可読性 ★★★ 高い ★★☆ 中程度

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

時間計算量 O(n)：すべてのノードをちょうど1回ずつ訪問するためです。最良ケース（根が葉）でも最悪ケース（全ノードを見る）でも、訪問回数は必ずノード数 n 以下に収まります。
空間計算量 O(h)：再帰呼び出しのたびに関数の情報がコールスタックに積まれます。その最大の深さが木の高さ h です。均衡した木では h ≈ log₂(n)（5000ノードで約12段）、一直線の木では h = n（最悪5000段）になります。

📖 用語集

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

▶ O(h)（スペース計算量）
h は木の高さ（Height）を表します。再帰呼び出しでは関数の呼び出し情報がスタックに積まれ、その深さが木の高さに比例します。均衡した木では O(log n)、一直線の木では O(n) になります。
▶ DFS（深さ優先探索）
Depth-First Search の略。木やグラフをできるだけ深く潜ってから引き返す探索方法です。迷路を一本道ずつ試すイメージです。根から葉への「パス」を追うのに向いています。BFS（幅優先探索）が横に広がるのに対して、DFS は縦に深く進みます。
▶ collections.deque（デック）
Python の標準ライブラリが提供するデータ構造で「両端開きの箱」のイメージです。前後どちらからでも O(1) で追加・取り出しができます。list は先頭への追加・削除が O(n) かかりますが、deque は O(1) です。スタックやキューとして使うのに最適です。
▶ コールスタック（Call Stack）
関数が呼び出されるたびにその情報（引数・ローカル変数・戻り先）を積み重ねる領域です。再帰関数は呼び出すたびにここに積まれ、返るたびに取り出されます。積みすぎると「スタックオーバーフロー」（Python では RecursionError）が発生します。
▶ 再帰（Recursion）
関数が自分自身を呼び出す仕組みです。木構造のように「同じ形が入れ子になった」データに対して自然に適用できます。ロシアのマトリョーシカ人形を開くように、同じ操作を繰り返して最終的に「これ以上開けない」（基底条件）に到達します。
▶ 再帰深度制限（Recursion Limit）
Python はデフォルトで再帰の深さを約 1000 に制限しています。sys.getrecursionlimit() で確認できます。5000 ノードの一直線の木では超過する可能性があるため、業務版では deque を使った反復 DFS で回避します。
▶ 短絡評価（Short-circuit Evaluation）
A or B という式で、A が True なら B を評価せずに即 True を返す仕組みです。今回の実装では左のサブツリーで答えが見つかった場合に右のサブツリー全体の探索をスキップできるため、最良ケースで処理を大幅に短縮できます。
▶ 葉（Leaf Node）
木において、左の子も右の子も存在しない末端のノードのことです。根から葉まで下りる一本道が「パス」であり、問題の条件は葉に到達したときにのみ確認します。葉でないノードで条件を確認してしまうと、途中で誤って答えを確定してしまうバグが起きます。
▶ ベースケース（Base Case）
再帰関数において「これ以上再帰呼び出しをしない」と判断して直接値を返す条件のことです。今回は「root is None」（空の木 or 存在しない子）と「葉ノードに到達した」の2つがベースケースです。ベースケースがないと関数が無限に呼ばれ続けてクラッシュします。