###### tags: `LeetCode` `Tree` `Recursion` `Medium`
# LeetCode #113 [Path Sum II](https://leetcode.com/problems/path-sum-ii/)
### (Medium)

給你二元樹的根節點 root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等於給定目標和的路徑。

葉子節點是指沒有子節點的節點。

---
宣告一個數組儲存現在路徑上經過的節點, 並且將該數組與目標數遞回傳入, 當某節點為葉子節點且它的值等於目標值時, 將整個數組插入答案數組。

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> tmp;
        helper(root, targetSum, ans, tmp);
        return ans;
    }
    void helper(TreeNode* node, int targetSum, vector<vector<int>> &ans, vector<int> tmp){
        if(!node)return;
        vector<int> tmp1(tmp);
        tmp1.push_back(node->val);
        if(targetSum==node->val&&!node->left&&!node->right){
            ans.push_back(tmp1);
            return;
        }
        targetSum-=node->val;
        if(node->left)helper(node->left, targetSum, ans, tmp1);
        if(node->right)helper(node->right, targetSum, ans, tmp1);
    }
};

---
可以看到上面的做法, 因為每一個路徑的節點組合都不同, 所以記錄用的數組不能共用, 原本的作法是傳入暫存數組後複製一份, 但這樣很耗費空間。

LeetCode的作法是傳入參考, 並且在最後pop掉暫存數組的尾端數字, 這樣就不會有互相影響的事情發生了。

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> tmp;
        helper(root, targetSum, ans, tmp);
        return ans;
    }
    void helper(TreeNode* node, int targetSum, vector<vector<int>> &ans, vector<int> &tmp){
        if(!node)return;
        tmp.push_back(node->val);
        if(targetSum==node->val&&!node->left&&!node->right){
            ans.push_back(tmp);
            tmp.pop_back();
            return;
        }
        targetSum-=node->val;
        if(node->left)helper(node->left, targetSum, ans, tmp);
        if(node->right)helper(node->right, targetSum, ans, tmp);
        tmp.pop_back();
    }
};