Path Sum III
題目描述
給定一棵二元樹和一個整數 targetSum。回傳路徑和等於 targetSum 的路徑數量。路徑方向必須向下（從父到子），但不需要從根開始或在葉結束。
輸入: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出: 3
解釋: 路徑 5→3, 5→2→1, -3→11 的和都等於 8
解題思路
初始化前綴和 Map
設 map[0] = 1，代表「前綴和為 0」出現 1 次，處理從根開始的路徑
DFS 遍歷
每到一個節點執行 currSum += node.val，累加從根到此的前綴和
查找配對
查 map[currSum - targetSum] 的值，即有幾個祖先的前綴和使得中間路徑和恰好等於 target
更新 Map
執行 map[currSum]++ 記錄當前前綴和出現次數，供子節點查找用
回溯
遞迴左右子樹後執行 map[currSum]--，移除當前節點的前綴和避免汙染其他分支
程式碼
C#
public class Solution {
public int PathSum(TreeNode root, int targetSum) {
var prefixMap = new Dictionary<long, int> { { 0, 1 } };
return Dfs(root, 0, targetSum, prefixMap);
}
private int Dfs(TreeNode node, long currSum, int target, Dictionary<long, int> map) {
if (node == null) return 0;
currSum += node.val;
// 有多少前綴和等於 currSum - target
int count = map.GetValueOrDefault(currSum - target, 0);
// 記錄當前前綴和
map[currSum] = map.GetValueOrDefault(currSum, 0) + 1;
count += Dfs(node.left, currSum, target, map);
count += Dfs(node.right, currSum, target, map);
// 回溯：離開此節點，移除此前綴和
map[currSum]--;
return count;
}
}TypeScript
function pathSum(root: TreeNode | null, targetSum: number): number {
const prefixMap = new Map<number, number>([[0, 1]]);
function dfs(node: TreeNode | null, currSum: number): number {
if (!node) return 0;
currSum += node.val;
// 有多少前綴和等於 currSum - target
let count = prefixMap.get(currSum - targetSum) ?? 0;
// 記錄當前前綴和
prefixMap.set(currSum, (prefixMap.get(currSum) ?? 0) + 1);
count += dfs(node.left, currSum);
count += dfs(node.right, currSum);
// 回溯：離開此節點，移除此前綴和
prefixMap.set(currSum, prefixMap.get(currSum)! - 1);
return count;
}
return dfs(root, 0);
}Python
from collections import defaultdict
def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
prefix_map = defaultdict(int)
prefix_map[0] = 1
def dfs(node, curr_sum):
if not node:
return 0
curr_sum += node.val
# 有多少前綴和等於 curr_sum - target
count = prefix_map[curr_sum - targetSum]
# 記錄當前前綴和
prefix_map[curr_sum] += 1
count += dfs(node.left, curr_sum)
count += dfs(node.right, curr_sum)
# 回溯：離開此節點，移除此前綴和
prefix_map[curr_sum] -= 1
return count
return dfs(root, 0)複雜度分析
| | Time | Space | |--|------|-------| | 前綴和解法 | O(n) | O(h) | | 暴力解法 | O(n²) | O(h) |
前綴和方法把每個節點的查找從 O(n) 降到 O(1)。Time O(n) 是因為每個節點訪問一次、HashMap 查找和更新都是 O(1)。暴力法 O(n^2) 是因為對每個節點都要往下遍歷整條路徑。Space O(h) 是因為 HashMap 最多同時存 h 個前綴和（一條根到葉的路徑），加上遞迴 call stack 深度 O(h)。
邊界情況
- 單一節點等於 target：根節點值等於 targetSum，前綴和 = target，map 中
target - target = 0出現 1 次，正確計數 - 所有節點值為 0，target 為 0：每條路徑和都是 0，前綴和會大量重複，需要正確計數所有組合
- 節點值有負數：前綴和可能先增後減，同一個前綴和值可能出現多次，HashMap 計數而非存在性檢查
圖解
圖表展示了前綴和的計算過程。以路徑 10→5→3 為例：前綴和 18，查找 18-8=10 在 map 中出現 1 次（根節點 10 的前綴和），代表從節點 5 開始到節點 3 的路徑和為 8。三條命中路徑分別是 5→3、5→2→1、-3→11。
進階觀點
💡面試追問
Q: 為什麼初始化 map[0] = 1？
A: 如果從根到某節點的前綴和恰好等於 targetSum，需要計入這條路徑。此時 currSum - target = 0，map 中必須有 0 對應的計數 1 才能正確命中。
Q: 為什麼要回溯（離開節點時 map[currSum]--）？ A: 前綴和只在「根到當前節點的路徑」上有效。如果不回溯，處理完左子樹後 map 中殘留左子樹的前綴和，右子樹會錯誤地匹配到不在同一路徑上的祖先前綴和。一維陣列版（LC 560）不需要回溯，因為不存在分支。
Q: 為什麼用 long 而不是 int？ A: 節點值可能很大，路徑上累加的前綴和可能溢出 int 範圍。C# 解法中 currSum 使用 long 型別來避免溢位。
變體題：LC 560 Subarray Sum Equals K（一維陣列版，不需回溯）、LC 113 Path Sum II（收集路徑而非計數）。
理解測驗
🤔 為什麼 DFS 離開節點時要把 prefixMap[currSum] 減 1？
🤔 相比暴力解法，前綴和方法的優勢是什麼？