class Solution {
public:
int recur(TreeNode* root, int sum, bool isHaveRoot) {
if(root == NULL) return 0;
int count = 0;
int val = root->val;
if(val == sum) count++;
if(root->left) {
// if haveroot, 则为保证路径连续,下个root也必须have
// so,if haveroot,必 - val,往下走
// if !haveroot, -val 和 不 -val 两条路往下走
if(!isHaveRoot)
count += recur(root->left, sum, false);
count += recur(root->left, sum - val, true);
}
if(root->right) {
if(!isHaveRoot)
count += recur(root->right, sum, false);
count += recur(root->right, sum - val, true);
}
return count;
}
int FindPath(TreeNode* root, int sum) {
// write code here
return recur(root, sum, false);
}
};