p437

 

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public int target;
	public HashSet<TreeNode> hashSet;

	public int pathSum(TreeNode root, int sum) {

		target = sum;
		hashSet = new HashSet<TreeNode>();
		return pathSum(root, sum, false);
	}

	public int pathSum(TreeNode root, int sum, boolean hasparent) {

		if (root == null)
			return 0;

		if (hashSet.contains(root) && !hasparent)
			return 0;
		if (!hasparent)
			hashSet.add(root);

		int count = sum == root.val ? 1 : 0;
		count += pathSum(root.left, sum - root.val, true);
		count += pathSum(root.right, sum - root.val, true);
		count += pathSum(root.left, target, false);
		count += pathSum(root.right, target, false);
		return count;
	}
}