算法思路

算法思路参考官方题解。由于要保存所有满足条件的路径，所以肯定要遍历二叉树。而且在遍历的过程中我们要保存所有满足题中条件的路径。

代码实现

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    using vvi = vector<vector<int>>; //using的新特性，vvi就表示vector<vector<int>>
    using vi = vector<int>;
    void dfs(TreeNode *root, int sum, vi &path, vvi &ret) {
        path.push_back(root->val);
        if (sum == root->val && !root->left && !root->right) {
            ret.push_back(path);
        }
        if (root->left) dfs(root->left, sum - root->val, path, ret);
        if (root->right) dfs(root->right, sum - root->val, path, ret);
        path.pop_back(); // 代码走到这里，表明要回溯，代表当前path中的root节点我已经不需要了
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vvi ret;
       	if(root==nullptr) return ret;
        vi path;
        dfs(root, expectNumber, path, ret);
        return ret;
    }
};

代码解析

我们定义了一个path容易来保存满足题中条件的路径。由于可能有着多条满足条件的路径，所以我们要在访问到叶子结点的时候要让path容器中的元素出去！这也是为什么dfs函数最后一行是 path.pop_back()。
这个解法的思路很简单，就是每次遍历一个结点，就让给定的sum值减去当前结点值，接着向下递归，所以我们每次递归第二个参数就是sum - root->val。（root代表当前结点）。最终走到叶子结点的时候就进行判断，满足条件就把这条路径放到答案容器ret中。

这道题的递归乍看没有出口，其实这个方法中都是条件判断，递归走到最后一层肯定满足不了条件，进而函数可以执行下去。