Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

5             / \            4   8           /   / \          11  13  4         /  \      \        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

C++代码：

#include
     
      #include
      
       #include
       
        using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public:    bool hasPathSum(TreeNode *root, int sum)    {        if(root->left==NULL&&root->right==NULL&&(sum-root->val)==0)            return true;        if(root->left)            return hasPathSum(root->left,sum-root->val);        if(root->right)            return hasPathSum(root->right,sum-root->val);        return false;    }    void createTree(TreeNode *&root)    {        int i;        cin>>i;        if(i!=0)        {            root=new TreeNode(i);            if(root==NULL)                return;            createTree(root->left);            createTree(root->right);        }    }};int main(){    Solution s;    TreeNode *root;    s.createTree(root);    if(s.hasPathSum(root,6))        cout<<"exist"<
       
      
     

运行结果：