题解 | #二叉树中和为某一值的路径(二)#

基于带记忆的DFS的解法，要用到回溯（栈）的方法，从而记录下来所有可能路径（而不是试通一个就结束）

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        if(root==nullptr)return{};
        vector<vector<int>> all_path={};
        CollectPath(root,expectNumber,all_path,{});//从根开始DFS
        return all_path;
        
    }
    //带记忆的DFS
    void CollectPath(TreeNode* root,int s,
                         vector<vector<int>>& all_path, vector<int> path)
    {
        //问题：每个节点出发只返回了一条路径(所以if改while)
        if(root==nullptr)return;
        path.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr
           &&root->val==s)
            {all_path.push_back(path);//收纳可行路径
            return; }
        CollectPath(root->left, s-root->val, all_path, path);
        CollectPath(root->right, s-root->val, all_path, path);
        path.pop_back();
    }

};