/**
 * 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<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }

    void dfs(TreeNode* root, int sum) {
        if (!root) return;//当前节点为空，则不是叶节点，直接return
        path.push_back(root->val);//将当前节点的值加入路径
        sum -= root->val;//做减法，减到0说明找到了一条路径
        if (!root->left && !root->right && !sum) ans.push_back(path);//左右儿子都为空则是叶节点，并且已经减到0，说明找到了一条路径
        dfs(root->left, sum);//递归左右子树
        dfs(root->right, sum);
        //下面两句的作用是恢复递归前的状态
        path.pop_back();
        /*
        dfs()函数里传进来的sum这个参数是值传递，
        函数内部对它的修改不会影响函数外面的值。
        所以最后对sum的恢复操作不管加不加，都没有任何影响。
        处于良好的模板习惯，还是加上比较好
        */
        sum +=root->val;//

    }
};