題目

給定一個二叉樹的根節點 root ，和一個整數 targetSum ，求該二叉樹里節點值之和等于 targetSum 的 路徑 的數目。
路徑 不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。

一、代碼實現（雙重遞歸法）

func pathSum(root *TreeNode, targetSum int) int {if root == nil {return 0}// 計算以當前節點為起點的路徑數 + 左右子樹的路徑數return dfs(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}func dfs(node *TreeNode, remain int) int {if node == nil {return 0}count := 0if node.Val == remain {count++}// 遞歸處理左右子樹，更新剩余目標值count += dfs(node.Left, remain - node.Val)count += dfs(node.Right, remain - node.Val)return count
}

---

二、算法分析（遞歸法）

1. 核心思路

• 雙重遞歸結構：外層遞歸遍歷所有節點作為路徑起點，內層遞歸計算以該節點為起點的路徑數目
• 暴力窮舉：對每個節點及其子樹進行深度優先搜索，統計符合條件的路徑

2. 關鍵步驟

1. 外層遞歸：遍歷每個節點作為可能的路徑起點
2. 內層遞歸：以當前節點為起點，向下搜索滿足sum=targetSum的路徑
3. 終止條件：空節點返回0，當前節點值等于剩余值時計數+1
4. 狀態傳遞：將剩余值remain - node.Val傳遞給子樹

3. 復雜度

指標	值	說明
時間復雜度	O(n2)	每個節點觸發一次O(n)的子樹遍歷
空間復雜度	O(h)	h為樹高度（遞歸棧空間）

---

三、代碼實現（前綴和優化法）

func pathSum(root *TreeNode, targetSum int) int {prefixSum := make(map[int]int)prefixSum[0] = 1 // 處理根節點自身滿足條件的情況return dfs(root, 0, targetSum, prefixSum)
}func dfs(node *TreeNode, currSum int, target int, prefixSum map[int]int) int {if node == nil {return 0}currSum += node.Valcount := prefixSum[currSum - target]prefixSum[currSum]++count += dfs(node.Left, currSum, target, prefixSum)count += dfs(node.Right, currSum, target, prefixSum)prefixSum[currSum]-- // 回溯return count
}

---

四、算法分析（前綴和法）

1. 核心思路

• 前綴和哈希表：記錄從根節點到當前節點的路徑和出現次數
• 數學關系：若存在currSum - target = oldSum，則oldSum -> currSum的路徑和為target

2. 關鍵步驟

1. 初始化哈希表：預存prefixSum[0]=1處理根節點自身滿足條件的情況
2. 更新當前和：累加節點值到currSum
3. 查詢差值：計算currSum - target的出現次數
4. 回溯操作：維護哈希表狀態避免子樹間的干擾

3. 復雜度

指標	值	說明
時間復雜度	O(n)	單次遍歷所有節點
空間復雜度	O(n)	哈希表存儲n個節點的前綴和

---

五、圖解示例

以root = [10,5,-3,3,2,null,11], targetSum=8為例：

        10/  \5   -3/ \    \3   2   11

前綴和法流程：

1. 路徑10→5→3：和為18 → 18-8=10（無記錄）
2. 路徑10→5→2：和為17 → 17-8=9（無記錄）
3. 路徑10→5：和為15 → 15-8=7（無記錄）
4. 路徑10→-3→11：和為18 → 18-8=10（命中初始0）
   最終計數：3（路徑5→3、路徑5→2→1、路徑-3→11）

---

六、邊界條件與擴展

1. 特殊場景驗證

• 空樹：返回0
• 負數和零：如root = [-2,null,-3], target=-5 → 返回1
• 重復路徑：多節點值相同的情況需正確計數

2. 擴展應用

• 多條件路徑統計：同時滿足和值與節點數限制
• 動態目標值：支持實時修改targetSum的在線查詢
• 路徑回溯：記錄具體路徑而非僅計數（需維護路徑棧）

---

七、總結與優化方向

1. 方法對比

方法	優勢	劣勢	適用場景
雙重遞歸	實現簡單	時間復雜度高	小規模樹(n<1000)
前綴和	線性時間復雜度	需要維護哈希表狀態	大規模樹

2. 工程優化

• 并行計算：對左右子樹進行并發遍歷（Go協程）
• 內存預分配：根據樹高度預判哈希表容量
• 數值溢出處理：使用int64存儲累加和

3. 算法擴展

• K路徑問題：統計和值為targetSum的TopK最長路徑
• 三維路徑：推廣到三叉樹等復雜結構
• 流式處理：支持無法完整加載內存的超大樹結構