113. Path Sum II

──────────────────────────────────────────────────────────────────────

113. Path Sum II

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

思路

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

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

為什麼需要回溯

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

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

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

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

收集答案時一定要複製

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

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

三題的階梯

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

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

解題方向

# 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 一樣要同時檢查「值對得上」和「是葉節點」，理由見那篇 —— 少了葉節點判斷會在路徑中途誤判。

補充

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

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

112. Path Sum —— 只問存不存在
257. Binary Tree Paths —— 列出所有根到葉路徑（不管總和），骨架和這題幾乎一樣
129. Sum Root to Leaf Numbers —— 把每條路徑當成一個數字再加總
437. Path Sum III —— 端點放寬

整理見 Tree 遍歷模板、Backtracking 模板。

複雜度

時間 $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)$ 。如果把它算進空間，那才是主導項 —— 面試時把「輸出佔的空間」和「演算法用的額外空間」分開講，會顯得比較清楚。