113. 路徑總和II

思路

判斷二叉樹從根結點走到葉節點的所有路徑中，經過的節點數值總和是targetSum。
把所有總和是targetSum的路徑記錄下來。

• curPath代表當前的路徑
• curSum代表當前路徑總和
• 從根結點往下走，當走到葉節點時，假如當前總和是targetSum，代表找到一個路徑，加入到答案當中。

走到一個節點時，先將當前節點的資訊加入，遞迴呼叫之後要回傳，在回傳時，還原成一開始的樣子。
比如呼叫dfs(root->left)時，先將left節點的資訊加入到curPath、curSum當中。
判斷是否為葉節點，如果是，看現在的路徑總和目標。不是就繼續往下走。在下面的路徑都走過之後，
還原成一開始的樣子。這樣dfs(root)才不會因為dfs(root->left)的改動而出錯。

程式碼

dfs

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(!root) return {};
        
        vector<vector<int>> res; // 最後答案
        vector<int> curPath;
        int curSum = 0;

        auto dfs = [&](this auto&&dfs, TreeNode* node) -> void {
            curPath.push_back(node->val);
            curSum += node->val;
            
            if(!node->left && !node->right) { // 走到葉節點，看總和是否為 targetSum
                if(curSum == targetSum) {
                    res.push_back(curPath);
                }
            }
            else {
                // 不是葉節點
                if(node->left) dfs(node->left); // 繼續往左走
                if(node->right) dfs(node->right); // 繼續往右走
            }

            curPath.pop_back();
            curSum -= node->val;
        };
        
        dfs(root);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$