解題說明
Path Sum III
題目描述：給定一棵二元樹的根節點 root 和整數 targetSum，找出所有路徑總和等於 targetSum 的路徑數量。路徑不必從根節點開始，也不必在葉節點結束，但必須沿著父子節點方向向下走（不可反向）。
解題思路：
最優解法是「Prefix Sum + Hash Map」，概念來自陣列子陣列和的經典技巧，延伸到樹上的 DFS 路徑。
核心觀察：若從根節點到目前節點的累計路徑和為 currSum，我們想找有多少條以某個祖先節點為起點、以目前節點為終點的路徑，其和恰好等於 targetSum。
等式整理：currSum - targetSum = prefixSum，也就是說，如果在之前走過的路徑上，存在某個祖先節點使得從根到該節點的前綴和等於 currSum - targetSum，那從該節點的下一個節點到目前節點的子路徑和就等於 targetSum。
因此，我們用一個 Hash Map prefixCount 紀錄「從根節點出發到每個已訪問節點的前綴和出現的次數」。在 DFS 過程中：
- 計算
currSum（根到目前節點的總和）。 - 查詢
prefixCount[currSum - targetSum]，即為新增的合法路徑數。 - 將
currSum加入prefixCount，再遞迴左右子樹。 - 回溯時從
prefixCount移除currSum，避免影響其他分支。
初始化時需放入 prefixCount[0] = 1，代表從根節點本身出發的路徑（前綴和為 0 的「空路徑」起點）。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點只被 DFS 訪問一次，Hash Map 的查詢與插入均為 O(1) 平均，因此整體為 O(n)，其中 n 為節點數量。
空間複雜度：O(n) — Hash Map 最多儲存從根到當前節點的路徑長度條前綴和，最壞情況（退化為鏈狀樹）為 O(n)；遞迴呼叫堆疊深度同樣為 O(n)。平衡樹時堆疊為 O(log n)，但 Hash Map 仍為 O(n)。
虛擬碼
1. Initialize prefixCount map with {0: 1} (one empty-path prefix)
2. Call dfs(root, currSum=0)
3. In dfs(node, currSum):
a. If node is null, return 0
b. currSum += node.val
c. count = prefixCount[currSum - targetSum] // paths ending here
d. prefixCount[currSum] += 1
e. count += dfs(node.left, currSum)
f. count += dfs(node.right, currSum)
g. prefixCount[currSum] -= 1 // backtrack
h. Return count
4. Return result of dfs(root, 0)其他解法
暴力雙重 DFS O(n²)：對每個節點都以它作為路徑起點，向下做一次完整的 DFS 搜尋是否能湊出 targetSum。外層遍歷所有節點 O(n)，內層 DFS 最壞 O(n)，整體 O(n²)。實作簡單直觀，但在節點數量大時效率明顯低於 Prefix Sum 解法。適合理解題意時的初步嘗試。
Prefix Sum 遞迴（有序 Map）O(n log n)：與最優解相同概念，但改用 map（紅黑樹）替代 unordered_map，查詢為 O(log n)，整體複雜度退化為 O(n log n)。在節點值分布極端（造成大量 hash collision）的特殊情況下，有序 map 的常數行為更穩定，但一般情況下不如 unordered_map。
延伸思考
- 如果路徑可以從任意節點出發、往任意方向走（包含向上），該如何計算滿足條件的路徑數？（提示：考慮 LeetCode 124 Binary Tree Maximum Path Sum 的思維。）
- 若樹的規模非常大（數百萬節點），且需要支援「動態插入節點後即時查詢路徑數」的操作，你會如何設計資料結構來加速？
- 如果將「路徑和等於 targetSum」改為「路徑和的餘數等於 targetSum mod k」，Prefix Sum 的技巧是否仍然適用？需要修改哪些地方？