引言

路徑總和系列是二叉樹遍歷中的經典問題，涵蓋從基礎遞歸到高級優化的多種解法。本文詳細分析LeetCode中路徑總和I、II、III的解題思路，并提供Java實現代碼與優化技巧，幫助讀者深入理解二叉樹遍歷與回溯算法的應用。

---

一、路徑總和 I（LeetCode 112）

問題描述

判斷二叉樹中是否存在從根節點到葉子節點的路徑，使得路徑節點值之和等于給定目標數。

方法思路

• 遞歸遍歷：深度優先搜索（DFS）遍歷每個節點。
• 終止條件：
  • 空節點直接返回false。
  • 葉子節點判斷當前剩余值是否等于節點值。
• 遞歸邏輯：對左右子樹遞歸檢查剩余目標值。

Java代碼實現

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;if (root.left == null && root.right == null) {return targetSum == root.val;}return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}
}

復雜度分析

• 時間復雜度：O(n)，每個節點訪問一次。
• 空間復雜度：O(n)，遞歸棧深度在最壞情況下（樹退化為鏈表）為n。

---

二、路徑總和 II（LeetCode 113）

問題描述

找出所有從根節點到葉子節點路徑和等于目標數的路徑，返回路徑列表。

方法思路

• 回溯法：通過動態維護路徑列表記錄當前路徑。
• 關鍵步驟：
  1. 添加當前節點到路徑。
  2. 到達葉子節點時檢查路徑和。
  3. 遞歸返回前移除當前節點（回溯）。

Java代碼實現

class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();dfs(root, targetSum, new ArrayList<>(), result);return result;}private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> result) {if (node == null) return;path.add(node.val);if (node.left == null && node.right == null && remain == node.val) {result.add(new ArrayList<>(path)); // 深拷貝路徑} else {dfs(node.left, remain - node.val, path, result);dfs(node.right, remain - node.val, path, result);}path.remove(path.size() - 1); // 回溯}
}

復雜度分析

• 時間復雜度：O(n)，每個節點訪問一次。
• 空間復雜度：O(n2)，存儲所有路徑的空間開銷。

---

三、路徑總和 III（LeetCode 437）

問題描述

統計路徑和等于目標數的路徑數量。路徑方向必須向下，但起點和終點不限制。

方法思路

• 前綴和+哈希表優化：
  • 記錄路徑前綴和及其出現次數。
  • 若當前前綴和為currentSum，查找currentSum - target是否存在。
• 回溯維護：遞歸后需清理當前前綴和，避免影響其他子樹。

Java代碼實現

class Solution {private int count = 0;private Map<Long, Integer> prefixMap = new HashMap<>();public int pathSum(TreeNode root, int targetSum) {prefixMap.put(0L, 1); // 初始化空路徑dfs(root, 0L, targetSum);return count;}private void dfs(TreeNode node, long currentSum, int target) {if (node == null) return;currentSum += node.val;count += prefixMap.getOrDefault(currentSum - target, 0);prefixMap.put(currentSum, prefixMap.getOrDefault(currentSum, 0) + 1);dfs(node.left, currentSum, target);dfs(node.right, currentSum, target);prefixMap.put(currentSum, prefixMap.get(currentSum) - 1); // 回溯}
}

復雜度分析

• 時間復雜度：O(n)，每個節點訪問一次。
• 空間復雜度：O(n)，哈希表存儲前綴和。

---

四、對比與總結

方法對比

問題	核心方法	時間復雜度	空間復雜度	關鍵難點
路徑總和 I	遞歸遍歷	O(n)	O(n)	終止條件判斷
路徑總和 II	回溯+路徑記錄	O(n)	O(n2)	深拷貝與回溯邏輯
路徑總和 III	前綴和+哈希表	O(n)	O(n)	前綴和統計與回溯維護

總結

1. 路徑總和I：基礎遞歸應用，理解終止條件與遞歸分解。
2. 路徑總和II：掌握回溯法維護路徑狀態，注意深拷貝避免引用問題。
3. 路徑總和III：前綴和優化是核心，通過空間換時間避免重復計算。

---

五、示例驗證

路徑總和II示例

輸入：

       5/ \4   8/   / \11  13  4/  \    / \7    2  5   1

目標值：22
輸出：[[5,4,11,2], [5,8,4,5]]

路徑總和III示例

輸入：

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

目標值：8
輸出：3（路徑為5→3, 5→2→1, -3→11）

---

通過系統化分析與代碼實現，讀者可深入掌握二叉樹路徑問題的多種解法，提升算法設計與優化能力。