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