Path Sum
Desicription
Given a binary tree and a sum, determine if the tree has a roottoleaf 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
,
1 2 3 4 5 6 7
 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1

return true, as there exist a roottoleaf path 5>4>11>2
which sum is 22.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { private: bool flag = 0; void searchTree(TreeNode* root, int sum, const int& target) { if(root == NULL  flag) return ; if(root>left == NULL && root>right == NULL) if(sum + root>val == target) flag = 1; searchTree(root>left, sum + root>val, target); searchTree(root>right, sum + root>val, target); } public: bool hasPathSum(TreeNode* root, int sum) { if(root == NULL) return 0; searchTree(root, 0, sum); return flag; } };
