437. Path Sum III

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

437. Path Sum III

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

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

思路

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

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

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

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

最直接的拆法是兩層：

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

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

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

解題方向

# 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 模板。

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

補充

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

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

能，用前綴和 + 雜湊表。 概念和 560. Subarray Sum Equals K 完全一樣，只是把「陣列上的區間」換成「根到當前節點的路徑」：

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

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

複雜度

雙層 DFS（本篇的寫法）

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

前綴和 + 雜湊表

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

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

437. Path Sum III

思路

解題方向

補充

這是 O(n2)，還有 O(n) 的解法

相關題

複雜度

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