深搜
思路: (1)从根节点开始往下搜索,遇到路径和等于expectNumber,并且当前节点为叶子节点时加入结果集; (2)注意,节点的值可以是负数,所以不能中断后续搜索。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
private:
vector<vector<int>> res;
vector<int> vec;
void helper(TreeNode* root, const int & expectNumber, int s){
if(root == NULL) return;
s += root -> val;
vec.push_back(root -> val);
if(s == expectNumber){
if(root -> left == NULL && root -> right == NULL){
res.push_back(vec);
}
}
helper(root -> left, expectNumber, s);
helper(root -> right, expectNumber, s);
vec.pop_back();
}
public:
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
helper(root, expectNumber, 0);
return res;
}
};