#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node * newnode(int x)
{
struct node *temp=new node;
temp->data=x;
temp->left=NULL;
temp->right=NULL;
return temp;
}
//vector<int> v;
int haspath(struct node* root,int sum,int level,int *count)
{
//v.push_back(root->data);
int flag=0;
if(root==NULL)
{
if(sum==0)
{
*count=(*count)+1;
cout<<count<<endl;
// for(int i=0;i<v.size();i++)
// {
// cout<<v[i];
// }
return 1;
}
return 0;
}
flag=haspath(root->left,sum-root->data,level+1,count) || flag;
flag=haspath(root->right,sum-root->data,level+1,count) || flag;
return flag;
}
int main() {
struct node* root = newnode(1);
root->left = newnode(10);
root->right = newnode(15);
root->left->left = newnode(5);
root->left->right = newnode(2);
int sum=16;
int level=0;
int count=0;
int ans= haspath(root,sum,level,&count);
cout<<ans<<endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7CglpbnQgZGF0YTsKCXN0cnVjdCBub2RlICpsZWZ0OwoJc3RydWN0IG5vZGUgKnJpZ2h0Owp9OwpzdHJ1Y3Qgbm9kZSAqIG5ld25vZGUoaW50IHgpCnsKCXN0cnVjdCBub2RlICp0ZW1wPW5ldyBub2RlOwoJdGVtcC0+ZGF0YT14OwoJdGVtcC0+bGVmdD1OVUxMOwoJdGVtcC0+cmlnaHQ9TlVMTDsKCXJldHVybiB0ZW1wOwp9CgovL3ZlY3RvcjxpbnQ+IHY7CgppbnQgaGFzcGF0aChzdHJ1Y3Qgbm9kZSogcm9vdCxpbnQgc3VtLGludCBsZXZlbCxpbnQgKmNvdW50KQp7CgkvL3YucHVzaF9iYWNrKHJvb3QtPmRhdGEpOwoJaW50IGZsYWc9MDsKCWlmKHJvb3Q9PU5VTEwpCgl7CgkJaWYoc3VtPT0wKQoJCXsKCQkJKmNvdW50PSgqY291bnQpKzE7CgkJCWNvdXQ8PGNvdW50PDxlbmRsOwoJCS8vCWZvcihpbnQgaT0wO2k8di5zaXplKCk7aSsrKQoJCS8vCXsKCQkvLwkJY291dDw8dltpXTsKCQkvLwl9CgkJCQoJCQlyZXR1cm4gMTsKCQl9CgkJcmV0dXJuIDA7Cgl9CgkKCQoJCglmbGFnPWhhc3BhdGgocm9vdC0+bGVmdCxzdW0tcm9vdC0+ZGF0YSxsZXZlbCsxLGNvdW50KSB8fCBmbGFnOwoJZmxhZz1oYXNwYXRoKHJvb3QtPnJpZ2h0LHN1bS1yb290LT5kYXRhLGxldmVsKzEsY291bnQpIHx8IGZsYWc7CgkKCXJldHVybiBmbGFnOwoJCgkKfQoKCmludCBtYWluKCkgewoJCglzdHJ1Y3Qgbm9kZSogcm9vdCA9IG5ld25vZGUoMSk7IAogICAgcm9vdC0+bGVmdCA9IG5ld25vZGUoMTApOyAKICAgIHJvb3QtPnJpZ2h0ID0gbmV3bm9kZSgxNSk7IAogICAgcm9vdC0+bGVmdC0+bGVmdCA9IG5ld25vZGUoNSk7IAogICAgcm9vdC0+bGVmdC0+cmlnaHQgPSBuZXdub2RlKDIpOyAKICAgIAogICAgaW50IHN1bT0xNjsKICAgIGludCBsZXZlbD0wOwogICAgaW50IGNvdW50PTA7CiAgICBpbnQgYW5zPSBoYXNwYXRoKHJvb3Qsc3VtLGxldmVsLCZjb3VudCk7CiAgICBjb3V0PDxhbnM8PGVuZGw7CgkKCQoJCgkKCQoJCglyZXR1cm4gMDsKfQ==