# 113 - Path Sum II

解法一 - recursion

我們可以利用 112 的做法，只是多用一個 vector 來記錄答案，用一個 vector 來記錄 path，只要每次發現 path sum 滿足，就把路徑加入答案。

/**
 * 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) {
        if(!root) return res;
        vector<int> path;

        findPath(root, sum, path);

        return res;
    }
private:
    vector<vector<int>> res;

    void findPath(TreeNode* root, int sum, vector<int> path) {
        if(!root) return;

        path.push_back(root->val);

        if(!root->left && !root->right && root->val == sum) {
            res.push_back(path);
            return;
        }

        findPath(root->left, sum-root->val, path);
        findPath(root->right, sum-root->val, path);
        path.pop_back();
        return;
    }
};

上面的實作因為是用 pass by value，所以會多耗很多記憶體跟時間，效能就不好：

Runtime: 32 ms, faster than 27.81% of C++ online submissions for Path Sum II. Memory Usage: 38.3 MB, less than 10.73% of C++ online submissions for Path Sum II.

如果修改一下程式碼，變成 pass by reference，效能就會好很多：

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> path;

        findPath(root, sum, path, res);

        return res;
    }

private:
    void findPath(TreeNode* root, int sum, vector<int> &path, vector<vector<int>> &res) {
        if(!root) return;

        path.push_back(root->val);

        if(!root->left && !root->right && root->val == sum) 
            res.push_back(path);

        findPath(root->left, sum-root->val, path, res);
        findPath(root->right, sum-root->val, path, res);
        path.pop_back();
    }
};

Runtime: 12 ms, faster than 95.70% of C++ online submissions for Path Sum II. Memory Usage: 20 MB, less than 54.29% of C++ online submissions for Path Sum II.