Given a binary tree and a sum , return true if the tree has a "root to leaf" path such that adding up all the values along the path equals the given sum. Return false if there is no path.
Strategy: subtract the node value from the sum when recurring down, and check to see if the sum is 0 when you run out of tree. */ bool hasPathSum(struct node* node, int sum) { /* return true if we run out of tree and sum==0 */ if (node == NULL) { return(sum == 0); } else { /* otherwise check both subtrees */ int subSum = sum - node->data; return(hasPathSum(node->left, subSum) || hasPathSum(node->right, subSum)); } }
Strategy: subtract the node value from the sum when recurring down,
ReplyDeleteand check to see if the sum is 0 when you run out of tree.
*/
bool hasPathSum(struct node* node, int sum)
{
/* return true if we run out of tree and sum==0 */
if (node == NULL)
{
return(sum == 0);
}
else
{
/* otherwise check both subtrees */
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}