Path Sum

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.

struct Node { int val; Node *left; Node *right; Node(int v) { val = v; left = right = NULL; } }; bool visit(Node *root, int target, int sum) { if (root == NULL) { return false; } if (root->left == NULL && root->right == NULL) { return root->val + sum == target; } return visit(root->left, target, sum + root->val) || visit(root->right, target, sum + root->val); } bool fun(Node *root, int target) { return visit(root, target, 0); }