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

# 113. Path Sum II

[113\. Path Sum II](https://leetcode.com/problems/path-sum-ii/)

列出**所有**從根到葉、節點值加起來等於 `targetSum` 的路徑。

## 思路

和 [112. Path Sum](/interview/coding/112-path-sum) 的遍歷方式完全一樣（一路往下把目標扣掉），但輸出從「存不存在」變成「列出全部」，這一步帶來一個新的需求：**必須記住走過的路徑**。

這就是回溯法登場的地方。這一題比較困難的地方在於，樹的遍歷之外還多了回溯的機制要維護。

### 為什麼需要回溯

要記路徑，最直覺的做法是「每次遞迴都傳一份新的 list 下去」（`go(node.left, acc + [node.val])`）。這樣是對的，但**每一層都在複製整條路徑**，會多花很多時間和記憶體。

回溯的做法是**只用同一個 list**：

- 進入節點時 `curr.append(node.val)`
- 離開節點時 `curr.pop()`

**這兩行必須成對**。少了 `pop`，走完左子樹回來時 `curr` 裡還留著左邊的節點，右子樹的路徑就會被污染。「做選擇 → 遞迴 → 撤銷選擇」是所有回溯題的固定骨架，見 [Backtracking 模板](/interview/coding/backtracking-template)。

### 收集答案時一定要複製

`result.append(list(curr))` 那個 `list(...)` 不能省。`curr` 從頭到尾是**同一個物件**，如果直接 `result.append(curr)`，收集到的全都是同一個參考 —— 回溯結束後 `curr` 被清空，`result` 裡就變成一堆空 list。

這是回溯題最常見的 bug，**只要是「收集答案」就要存快照**。

### 三題的階梯

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

437 會沿用這題的回溯機制，但它真正的新難點是端點放寬 —— 所以這題的 `append` / `pop` 一定要先寫熟。

## 解題方向

```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) -> List[List[int]]:

        result = []
        def backtrack(node, targetSum, curr):
            if not node:
                return 

            curr.append(node.val)
            if node.val == targetSum and not node.left and not node.right:
                result.append(list(curr))
            else:
                backtrack(node.left, targetSum - node.val, curr)
                backtrack(node.right, targetSum - node.val, curr)
            curr.pop()

        backtrack(root, targetSum, [])
        return result
```

幾個關鍵：

- **`curr.pop()` 在 `if/else` 外面**，所以不管走哪一條分支都會執行。如果把它寫進 `else` 裡，找到答案的那條路徑就不會被還原，後面全錯。
- **`else` 是小小的剪枝**：已經確認是符合條件的葉節點了，它沒有子節點，不需要再往下遞迴。拿掉 `else` 改成無條件遞迴也對（葉節點的子樹是 `None`，一進去就返回），只是多兩次無效呼叫。
- **終止條件和 [112](/interview/coding/112-path-sum) 一樣要同時檢查「值對得上」和「是葉節點」**，理由見那篇 —— 少了葉節點判斷會在路徑中途誤判。

## 補充

**節點值可以是負數**，所以不能用「剩餘目標小於 0 就剪枝」這種優化，往下走可能先變小再變大。

**同一家族的其他題**（都是根到葉，只是輸出不同）：

- [112. Path Sum](/interview/coding/112-path-sum) —— 只問存不存在
- [257. Binary Tree Paths](/interview/coding/257-binary-tree-paths) —— 列出所有根到葉路徑（不管總和），骨架和這題幾乎一樣
- [129. Sum Root to Leaf Numbers](/interview/coding/129-sum-root-to-leaf-numbers) —— 把每條路徑當成一個數字再加總
- [437. Path Sum III](/interview/coding/437-path-sum-iii) —— 端點放寬

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)、[Backtracking 模板](/interview/coding/backtracking-template)。

## 複雜度

- 時間 $O(n^2)$ 最壞 — 走訪是 $O(n)$，但每找到一條符合的路徑要花 $O(h)$ 複製；最壞情況（例如一棵每條路徑都符合的完全二元樹）有 $O(n)$ 條路徑、每條長 $O(\log n)$，實務上遠低於 $O(n^2)$，但要講得出「複製路徑的成本不能忽略」
- 空間 $O(h)$ — 遞迴堆疊加上 `curr`，兩者都不超過樹高（不含輸出的 `result`）

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

**輸出本身可能很大**：最壞情況所有根到葉路徑都符合，總輸出量是 $O(n \cdot h)$。如果把它算進空間，那才是主導項 —— 面試時把「輸出佔的空間」和「演算法用的額外空間」分開講，會顯得比較清楚。