437. Path Sum III 发表于 2021-11-14 DFS123456789101112131415161718192021222324252627282930313233class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } // 从当前节点向下满足路径和的路径数量 int pathCount = dfs(root, targetSum); // 因为题目要求路径不需要从根节点开始,即从任意节点开始均可,所以需要以下两行递归调用,注意对 pathSum 是递归调用 pathCount += pathSum(root.left, targetSum); pathCount += pathSum(root.right, targetSum); return pathCount; } private int dfs(TreeNode node, int targetSum) { if (node == null) { return 0; } int pathCount = 0; if (node.val == targetSum) { pathCount++; } pathCount += dfs(node.left, targetSum - node.val); pathCount += dfs(node.right, targetSum - node.val); return pathCount; }} Backtracking + Prefix Sum123456789101112131415161718192021class Solution { public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> prefixSumToCountMap = new HashMap<>(); prefixSumToCountMap.put(0L, 1); return dfs(prefixSumToCountMap, root, 0, targetSum); } private int dfs(Map<Long, Integer> prefixSumToCountMap, TreeNode node, long prefixSum, int targetSum) { if (node == null) { return 0; } prefixSum += node.val; int pathCount = prefixSumToCountMap.getOrDefault(prefixSum - targetSum, 0); // 注意此处是 prefixSum - targetSum, 不要搞反了 prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.getOrDefault(prefixSum, 0) + 1); pathCount += dfs(prefixSumToCountMap, node.left, prefixSum, targetSum); pathCount += dfs(prefixSumToCountMap, node.right, prefixSum, targetSum); prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.get(prefixSum) - 1); return pathCount; }} Reference437. Path Sum III剑指 Offer II 050. 向下的路径节点之和