Reference no: EM132206629
Question :
Write a method that returns 1 if there is a root-to-leaf path whose node values sum to target and returns 0 if there is no such root-to-leaf path.
For example, in the tree below there are exactly four root-to-leaf paths. The sums on these paths are 27, 22, 26, 18, so hasPathSum(22,tree) will return 1 for the tree shown and hasPathSum(32,tree) will return 0 for the tree shown.
Note that an empty tree will always return 0, regardless of the value oftarget. Similarly, a tree with exactly one node will result in returning 1 if target is the value in the node, and zero otherwise.
The TreeNode class will be accessible when your method is tested.
public class TreeNode { int info;
TreeNode left;
TreeNode right;
TreeNode(int x){
info = x;
}
TreeNode(int x, TreeNode lNode, TreeNode rNode)
{ info = x; left = lNode; right = rNode; } }
skeleton code is provided below:
public class PathSum {
public int hasPath(int target TreeNode tree){
// replace with working code
return 0; } }
Examples:
target = 5 tree = {5,x,x}
Returns 1, there is a path whose sum is target
target = 4 tree = {5,x,x}
Returns 0, there is no path that sums to 5
target = 18 tree = {5, 4, 11, 7, x, x, 2, x, x, x, 8, 13, x, x, 4, x, 1, x, x}
Returns 1, this is the tree diagrammed above