---
title: "437. Path Sum III"
url: "https://laigary.com/interview/coding/437-path-sum-iii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Prefix Sum", "Tree", "Depth-First Search"]
---

# 437. Path Sum III

[437\. Path Sum III](https://leetcode.com/problems/path-sum-iii/)

更難的樹的遍歷加上回溯法。

數出樹裡有幾條路徑的和等於 `targetSum`。路徑**不必從根開始、也不必在葉節點結束**，但方向必須由上往下。

## 思路

和 [112. Path Sum](/interview/coding/112-path-sum)、[113. Path Sum II](/interview/coding/113-path-sum-ii) 的差別就在那句「**不必從根開始**」。前兩題只要一趟 DFS，這題的路徑可以從任何節點起頭，所以起點本身也要枚舉。

三題各自放寬了不同的東西：

| | 起點 | 終點 | 要回傳什麼 | 新增的難點 |
|---|---|---|---|---|
| [112. Path Sum](/interview/coding/112-path-sum) | 根 | 葉 | 存不存在（`bool`） | — |
| [113. Path Sum II](/interview/coding/113-path-sum-ii) | 根 | 葉 | **所有**路徑（`list`） | 要**回溯**（記路徑、離開時還原） |
| **437 這題** | **任意** | **任意** | 數量（`int`） | **端點放寬** → 要枚舉起點 |

這題**沿用** 113 的回溯機制（下面的 `curr.append` / `curr.pop` 就是），但真正的新難點是端點放寬 —— 那是 112 / 113 都沒有的第三個軸，也是為什麼這題才有「前綴和」那條完全不同的優化路線（端點自由，「前綴和相減」才派得上用場）。

最直接的拆法是兩層：

1. **外層**：走訪每一個節點，把它當成路徑的起點
2. **內層**：從那個起點往下走，累加路徑和，等於 `targetSum` 就計數

內層是「從固定起點往下找」，正好就是 112 那題。所以這題又是**「已知題當子程序 + 外面包一層遍歷」**的結構 —— 和 [572. Subtree of Another Tree](/interview/coding/572-subtree-of-another-tree) 一樣。

實作上不必真的重新累加：**每往下一層就把目標減去當前節點的值**，目標歸零時就代表這一段的和剛好等於原本的 `targetSum`。這樣就不用另外維護一個累加變數。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        if not root:
            return 0
        result = []
        def backtrack(node, targetSum, curr):
            if not node:
                return 

            curr.append(node.val)
            if node.val == targetSum:
                result.append(list(curr)) 

            backtrack(node.left, targetSum - node.val, curr)
            backtrack(node.right, targetSum - node.val, curr)
            curr.pop()

        def dfs(node):
            backtrack(node, targetSum, [])
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
        dfs(root)
        return len(result)
```

`dfs` 是外層（枚舉起點），`backtrack` 是內層（從起點往下）。

`if node.val == targetSum` 這行看起來像在比單一節點的值，其實不是 —— **`targetSum` 已經被上面每一層減過了**，所以這個等式等價於「從起點到我的累加和 == 原本的 targetSum」。這是很精簡的寫法，但也因此容易看不懂，寫註解或改成維護 `curr_sum` 都會更好讀。

`curr.append(...)` 配 `curr.pop()` 是標準的回溯：進去時加、離開時還原，讓同一個 list 在整棵樹裡重複使用。見 [Backtracking 模板](/interview/coding/backtracking-template)。

**一個可以省的地方**：`result` 存了每一條完整路徑，但最後只用到 `len(result)`。題目只要數量，所以用一個計數器就夠，可以省下 $O(n)$ 的路徑儲存。要留著路徑內容的話，那是 113 那題在做的事。

## 補充

### 這是 $O(n^2)$，還有 $O(n)$ 的解法

外層每個節點都要跑一次內層 DFS，所以最壞（斜樹）是 $O(n^2)$、平衡樹是 $O(n \log n)$。

**能，用前綴和 + 雜湊表。** 概念和 [560. Subarray Sum Equals K](/interview/coding/560-subarray-sum-equals-k) 完全一樣，只是把「陣列上的區間」換成「根到當前節點的路徑」：

- 一路往下維護「從根到我的累加和」`curr_sum`
- 想知道「有幾條以我結尾的路徑和是 `target`」，就等於問「**前面有幾個祖先的前綴和等於 `curr_sum - target`**」
- 用一個 hash table 記下沿途每個前綴和出現的次數，就能 $O(1)$ 查到
- **離開一個節點時要把它的前綴和從表裡減掉**（回溯），否則會算到不在同一條路徑上的節點

我沒有用這個角度寫過這題，所以這裡不展開程式碼；但知道「路徑和問題 → 前綴和 + hash」這條線，並說得出「這跟 560 是同一招」，在面試裡就夠用了。

### 相關題

[112. Path Sum](/interview/coding/112-path-sum)（根到葉、只問有沒有）、[113. Path Sum II](/interview/coding/113-path-sum-ii)（根到葉、要列出所有路徑）、[129. Sum Root to Leaf Numbers](/interview/coding/129-sum-root-to-leaf-numbers)、[124. Binary Tree Maximum Path Sum](/interview/coding/124-binary-tree-maximum-path-sum)（路徑可以轉彎，是另一型）。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

**雙層 DFS（本篇的寫法）**
- 時間 $O(n^2)$ 最壞（斜樹）、$O(n \log n)$ 平衡 — 外層 `n` 個起點，每個起點的內層要走完它的子樹
- 空間 $O(n)$ — 遞迴堆疊 $O(h)$，加上 `result` 存下所有符合的路徑；只計數的話可以降到 $O(h)$

**前綴和 + 雜湊表**
- 時間 $O(n)$ — 每個節點只走一次
- 空間 $O(h)$ — hash table 裡最多同時存一條根到葉路徑上的前綴和

其中 `n` 是節點數、`h` 是樹高。