@@ -0,0 +1,2227 @@
+package fundamentals.tree.dfs.leaf.lc437_pathsum3;%0A%0Aimport fundamentals.tree.TreeNode;%0A%0A/**%0A * You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value.%0A * The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).%0A */%0Apublic class Solution %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        TreeNode root = new TreeNode(10);%0A        root.left = new TreeNode(5);%0A        root.left.left = new TreeNode(3);%0A        root.left.right = new TreeNode(2);%0A        root.left.left.left = new TreeNode(3);%0A        root.left.left.right = new TreeNode(-2);%0A        root.left.right.right = new TreeNode(1);%0A        root.right = new TreeNode(-3);%0A        root.right.right = new TreeNode(11);%0A        System.out.println(new Solution().pathSum1(root, 8, 0));%0A    %7D%0A%0A    // O(N%5E2) time worst case, O(NlogN) time for balanced tree.%0A    public int pathSum(TreeNode root, int sum) %7B%0A        if (root == null) return 0;%0A        return dfs(root, 0, sum) +%0A                pathSum(root.left, sum) + // Wrong if call dfs(root.left, root.val+sum, target)%0A                pathSum(root.right, sum); // Since val+sum path in subtree doesn't connect to root necessrialy.%0A    %7D%0A%0A    private int dfs(TreeNode root, int sum, int target) %7B%0A        if (root == null) return 0;%0A        return (root.val + sum == target ? 1 : 0) +%0A                dfs(root.left, root.val + sum, target) +%0A                dfs(root.right, root.val + sum, target);%0A    %7D%0A%0A    // Wrong! Subtree has sum-root.val(8-5) path, but it doesn't mean it is connected to root to form a path = original sum 8.%0A    public int pathSum1(TreeNode root, int sum, int depth) %7B%0A        if (root == null) return 0;%0A        int ret = (root.val == sum ? 1 : 0) +%0A                pathSum1(root.left, sum, depth + 1) +%0A                pathSum1(root.right, sum, depth + 1) +%0A                pathSum1(root.left, sum - root.val, depth + 1) +%0A                pathSum1(root.right, sum - root.val, depth + 1);%0A        while (depth-- %3E 0) System.out.printf(%22%5Ct%22);%0A        System.out.printf(%22Node %25d get result %25d%5Cn%22, root.val, ret);%0A        return ret;%0A    %7D%0A%0A%7D%0A

path sum III