题解 | #二叉树中和为某一值的路径(二)#
二叉树中和为某一值的路径(二)
http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
跟前一个题差不多，唯一的区别是深度优先遍历的参数稍作调整。
路径回退的时候需要pop当前路径，这个要注意一下。
记录路径当然要有当前路径，最后的结果也需要记录。
/*
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) {
vector<vector<int>> endPath;
vector<int> curPath;
dfs(root,expectNumber,0,curPath,endPath);
return endPath;
}
void dfs(TreeNode* root,int expectNumber,int cur,vector<int> &curPath,vector<vector<int>> &endPath){
if(root == NULL){
return;
}
curPath.push_back(root->val);
if(root->left){
dfs(root->left,expectNumber,cur+root->val,curPath,endPath);
curPath.pop_back();
}
if(root->right){
dfs(root->right,expectNumber,cur+root->val,curPath,endPath);
curPath.pop_back();
}
if(root->left == NULL && root->right == NULL){
if(cur+root->val == expectNumber){
endPath.push_back(curPath);
}
}
}
};
