package leetcode.easy;

/**

 * Definition for a binary tree node. public class TreeNode { int val; TreeNode

 * left; TreeNode right; TreeNode(int x) { val = x; } }

 */

public class PathSumIII {

	int count = 0;

	private void helper(TreeNode root, int sum) {

		if (root == null) {

			return;

		}

		if (root.val == sum) {

			count++;

		}

		if (root.left != null) {

			helper(root.left, sum - root.val);

		}

		if (root.right != null) {

			helper(root.right, sum - root.val);

		}

	}

	public int pathSum(TreeNode root, int sum) {

		if (root == null) {

			return count;

		}

		helper(root, sum);

		if (root.left != null) {

			pathSum(root.left, sum);

		}

		if (root.right != null) {

			pathSum(root.right, sum);

		}

		return count;

	}

	@org.junit.Test

	public void test() {

		int sum = 8;

		TreeNode tn11 = new TreeNode(10);

		TreeNode tn21 = new TreeNode(5);

		TreeNode tn22 = new TreeNode(-3);

		TreeNode tn31 = new TreeNode(3);

		TreeNode tn32 = new TreeNode(2);

		TreeNode tn34 = new TreeNode(11);

		TreeNode tn41 = new TreeNode(3);

		TreeNode tn42 = new TreeNode(-2);

		TreeNode tn44 = new TreeNode(1);

		tn11.left = tn21;

		tn11.right = tn22;

		tn21.left = tn31;

		tn21.right = tn32;

		tn22.left = null;

		tn22.right = tn34;

		tn31.left = tn41;

		tn31.right = tn42;

		tn32.left = null;

		tn32.right = tn44;

		tn34.left = null;

		tn34.right = null;

		tn41.left = null;

		tn41.right = null;

		tn42.left = null;

		tn42.right = null;

		tn44.left = null;

		tn44.right = null;

		System.out.println(pathSum(tn11, sum));

	}

}