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

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> >ret;
    vector<int>path;
    void dfs(TreeNode* root,int sum){
        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);
        if(root->right)dfs(root->right,sum-root->val);
        path.pop_back();//到这一步需要回溯
    }
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        if(!root)return ret;//为空直接返回

        dfs(root,expectNumber);
        return ret;
    }
};