EEPW论坛

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 andsum = 22,

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

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

1. class Solution {  

2. public:  

3.     bool hasPathSum(TreeNode* root, int sum)  

4.     {  

5.         if (root==NULL)  

6.         {  

7.             return false;  

8.         }  

9.   

10.         if (root->right==NULL && root->left==NULL && sum-root->val==0)  

11.         {  

12.             return true;  

13.         }  

14.   

15.         return hasPathSum(root->left, sum-root->val ) || hasPathSum(root->right, sum - root->val);  

16.     }  

17. };  

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.

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

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