import java.util.HashMap; public class PathSumIII { /** * 当root.val == Sum时，不要return，因为继续往下走可能有路径刚好加起来为0，典型的为[1,-2,1,-1]，目标和为-1 * 这里隐藏了四条路径，[1,-2], [-2,1], [-1], [1,-2,1,-1]，如果在[1,-2]就return了，那就会掉了[1,-2,1,-1] * 可参考https://discuss.leetcode.com/category/562/path-sum-iii */ /** * 有两种可能，算上当前root和不算当前root */ public int pathSum(TreeNode root, int sum) { int[] count = new int[1]; helperSum(root, sum, count); return count[0]; } /** * 既可以算上，也可以不算上root */ private void helperSum(TreeNode root, int sum, int[] count) { if (root == null) { return; } // 算上root helper(root, sum, count); // 不算上root helperSum(root.left, sum, count); helperSum(root.right, sum, count); } /** * 算上root */ private void helper(TreeNode root, int sum, int[] count) { if (root == null) { return; } if (root.val == sum) { count[0]++; // 这里不用返回，因为下面的路径和可能为0; } helper(root.left, sum - root.val, count); helper(root.right, sum - root.val, count); } /** * 更优化的写法，时间复杂度O(n) * 和Two Sum较类似，都是算出从root到当前节点的和，target为两段和的差值 */ public int pathSum2(TreeNode root, int sum) { HashMap map = new HashMap<>(); map.put(0, 1); int[] count = new int[1]; helper(root, sum, 0, map, count); return count[0]; } private void helper(TreeNode node, int target, int sum, HashMap map, int[] count) { if (node == null) { return; } sum += node.val; if (map.containsKey(sum - target)) { count[0] += map.get(sum - target); } map.put(sum, map.getOrDefault(sum, 0) + 1); helper(node.left, target, sum, map, count); helper(node.right, target, sum, map, count); map.put(sum, map.getOrDefault(sum, 0) - 1); } }