Sunday, 9 October 2016

Root to leaf path sum equal to a given number

Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number. Return false if no such path can be found.

Solution:

boolean hasPathSum(TreeNode node, int sum) {
if (node == null) {
return false;
}
int subsum = sum - node.val;
if (node.left == null && node.right == null && subsum == 0) {
return true;
}
return hasPathSum(node.left, subsum) 
|| hasPathSum(node.right, subsum);
}

No comments:

Post a Comment