Path Sum III

1package pkg5leetcode.official75;2 3/*4 * Path Sum III | LC 4375 * APPROACH: Prefix sum on tree paths with hash map.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class official75_LC437PathSumIII {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static int pathSum(TreeNode root, int targetSum) {20        Map<Long, Integer> prefix = new HashMap<>();21        prefix.put(0L, 1);22        return dfs(root, 0L, targetSum, prefix);23    }24 25    static int dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {26        if (node == null) return 0;27        cur += node.val;28        int count = prefix.getOrDefault(cur - target, 0);29        prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);30        count += dfs(node.left, cur, target, prefix);31        count += dfs(node.right, cur, target, prefix);32        prefix.put(cur, prefix.get(cur) - 1);33        return count;34    }35 36    public static void main(String[] args) {37        TreeNode root = new TreeNode(10);38        root.left = new TreeNode(5); root.right = new TreeNode(-3);39        root.left.left = new TreeNode(3); root.left.right = new TreeNode(2);40        root.right.right = new TreeNode(11);41        root.left.left.left = new TreeNode(3); root.left.left.right = new TreeNode(-2);42        root.left.right.right = new TreeNode(1);43        check(pathSum(root, 8) == 3, "case1");44        TreeNode r2 = new TreeNode(5);45        check(pathSum(r2, 5) == 1, "case2");46        System.out.println("all tests passed");47    }48 49    static void check(boolean cond, String name) {50        if (!cond) throw new AssertionError("FAILED: " + name);51        System.out.println("  PASS " + name);52    }53}