LeetCode 113 Path Sum II：DFS 回溯尋找所有路徑和

題目大意

給定二叉樹根節點 root 與目標和 targetSum。找出所有從根到葉子節點的路徑，使得路徑上節點值之和等於 targetSum。回傳路徑列表（每條路徑為節點值序列）。

範例：

      5
     / \
    4   8
   /   / \
  11  13  4
 / \     / \
7   2   5   1
targetSum = 22
輸出：[[5,4,11,2], [5,8,4,5]]

解法：遞歸 DFS + 回溯

維護當前路徑 path（動態陣列）與當前累積和 curSum。遞歸進入節點時將節點值加入 path 並更新 curSum；遇到葉子節點檢查是否等於目標，是則將 path 複製加入結果；遞歸返回前將節點值從 path 移除（回溯）。

關鍵點

• 傳遞 path 參考，遞歸結束後 pop_back() 還原狀態。
• 結果儲存 path 的副本（clone() 或構造新 List），避免後續修改影響已存路徑。
• 空樹回傳空列表。

Java 完整實現

import java.util.*;

public class PathSumII {
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) dfs(root, sum, 0, new ArrayList<>(), result);
        return result;
    }

    private static void dfs(TreeNode root, int target, int curSum,
                            ArrayList<Integer> path, List<List<Integer>> result) {
        // 加入當前節點
        path.add(root.val);
        curSum += root.val;

        // 葉子節點檢查
        if (root.left == null && root.right == null) {
            if (curSum == target) {
                result.add(new ArrayList<>(path)); // 複製副本
            }
        } else {
            if (root.left != null) dfs(root.left, target, curSum, path, result);
            if (root.right != null) dfs(root.right, target, curSum, path, result);
        }

        // 回溯：移除當前節點
        path.remove(path.size() - 1);
    }

    // 測試用 TreeNode 定義
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(-2);
        TreeNode n3 = new TreeNode(-3);
        TreeNode n4 = new TreeNode(1);
        TreeNode n5 = new TreeNode(3);
        TreeNode n6 = new TreeNode(-2);
        TreeNode n7 = new TreeNode(-1);
        n1.left = n2; n1.right = n3;
        n2.left = n4; n2.right = n5;
        n3.left = n6;
        n4.left = n7;
        System.out.println(pathSum(n1, 2));
    }
}

複雜度分析

• 時間：O(N) 遍歷每個節點一次；複製路徑總長度至多 O(N log N)（平衡樹）或 O(N^2)（退化鏈），整體 O(N^2) 最壞情況。
• 空間：遞歸棧深度 O(H)（H 為樹高），路徑存儲 O(H)，結果輸出空間不計入。

Python 簡潔版本

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(node, path, cur):
            if not node: return
            path.append(node.val)
            cur += node.val
            if not node.left and not node.right and cur == targetSum:
                res.append(path[:])  # 複製
            dfs(node.left, path, cur)
            dfs(node.right, path, cur)
            path.pop()
        dfs(root, [], 0)
        return res