算法思路

该题意与 LeetCode 112. 路径总和 相同，但是上一题只需要判断是否存在合法方案，该题需要返回合法路径。因此在上一题的基础上，需要利用路径数组存储遍历到的结点。

注意：该题最重要的地方是对路径数组进行回溯，当遍历到一个结点时，此时有两条路可走，一条是向左走，一条是向右走，每走完一边后，记得将放入路径中的该点弹出。

C ++代码

/**
 * 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>> res;
    vector<int> path; //路径数组
    int s;
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (!root) return res;
        s = sum;
        dfs(root, 0);
        return res; 
    }

    void dfs(TreeNode* u, int sum)
    {
        path.push_back(u -> val); //遍历该点加入路径
        sum += u -> val;
        if (!u -> left && !u -> right)
        {
            if (sum == s) res.push_back(path);
            return;
        }

        if (u -> left)
        {
             dfs(u -> left, sum);
             path.pop_back(); //回溯
        }

        if (u -> right) 
        {
            dfs(u -> right, sum);
            path.pop_back(); //回溯
        }
    }
};