LeetCode Path Sum II：尋找所有根到葉路徑和為目標值的路徑

題目描述

給定二叉樹根節點 root 和目標和 sum，找出所有從根節點到葉子節點的路徑，使得路徑上節點值之和等於 sum。返回所有滿足條件的路徑列表。

示例：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], sum = 22
輸出：[[5,4,11,2], [5,8,4,5]]

遞歸回溯解法

核心思路

• 深度優先搜索（DFS）遍歷樹
• 維護當前路徑 path（值類型傳遞，自動回溯）
• 到達葉子節點時，檢查剩餘和是否為 0
• 滿足條件則將 path 加入結果集

代碼實現

class Solution {
public:
    vector> pathSum(TreeNode* root, int sum) {
        vector> res;
        vector path;
        dfs(root, sum, path, res);
        return res;
    }
private:
    void dfs(TreeNode* node, int sum, vector& path, vector>& res) {
        if (!node) return;
        path.push_back(node->val);
        if (!node->left && !node->right) { // 葉子節點
            if (node->val == sum) res.push_back(path);
        } else {
            dfs(node->left, sum - node->val, path, res);
            dfs(node->right, sum - node->val, path, res);
        }
        path.pop_back(); // 回溯
    }
};

關鍵細節

1. 值傳遞 vs 引用傳遞：path 用引用傳遞並在調用前後 push_back/pop_back，避免每層遞歸拷貝向量，空間 O(h)
2. 葉子節點判斷：!left && !right，非葉子節點不判斷和
3. 剩餘和傳遞：遞歸參數傳 sum - node->val，葉子處直接比較 node->val == sum，邏輯清晰
4. 空樹處理：根為空直接返回空結果

複雜度分析

• 時間：O(n) 訪問每個節點一次，路御拷貝總長度 ≤ nh（最壞情況斜樹）
• 空間：O(h) 遞歸棧 + 當前路徑，h 為樹高

迭代版本（棧模擬）

vector> pathSum(TreeNode* root, int sum) {
    vector> res;
    if (!root) return res;
    stack>> st;
    st.emplace(root, sum, vector());
    while (!st.empty()) {
        auto [node, rem, path] = st.top(); st.pop();
        path.push_back(node->val);
        if (!node->left && !node->right && node->val == rem)
            res.push_back(path);
        if (node->right) st.emplace(node->right, rem - node->val, path);
        if (node->left) st.emplace(node->left, rem - node->val, path);
    }
    return res;
}

注意：迭代版 path 為值傳遞（每次入棧拷貝），空間較大，但避免遞歸棧溢出風險。

總結

Path Sum II 是經典樹形 DP/回溯問題。遞歸版代碼簡潔、符合直覺，工程首選；迭代版適合深度極大場景。核心模式：DFS + 路御記錄 + 葉子判斷 + 回溯，可擴展至路御和、路御乘積、路御字符串等變體。