LeetCode 113：Path Sum II（路徑總和 II）

一、題目描述

給定一棵二叉樹和一個目標和 sum，找出所有從根節點到葉子節點路徑總和等於目標和的路徑。

範例：

給定二叉樹：
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

sum = 22

返回：
[
   [5,4,11,2],
   [5,8,4,5]
]

二、解題思路：DFS 回溯

使用前序遍歷（根-左-右），維護一條當前路徑 path 和剩餘目標和 remaining：

1. 將當前節點值加入 path，更新 remaining -= node.val。
2. 若到達葉子節點且 remaining == 0，將 path 加入結果集。
3. 遞歸處理左、右子樹。
4. 回溯：從 path 移除當前節點值。

三、代碼實現（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(root, sum, path, result);
        return result;
    }

private:
    void dfs(TreeNode* node, int remaining, vector<int>& path, vector<vector<int>>& result) {
        if (!node) return;
        path.push_back(node->val);
        if (!node->left && !node->right && node->val == remaining) {
            result.push_back(path);
        }
        dfs(node->left, remaining - node->val, path, result);
        dfs(node->right, remaining - node->val, path, result);
        path.pop_back(); // 回溯
    }
};

四、複雜度分析

• 時間複雜度：O(N^2) 最壞情況（樹退化為鏈表，每條路徑複製耗時 O(N)）
• 空間複雜度：O(N) 遞歸棧 + 路徑存儲