java 解法一：雙遞歸

class Solution {public int pathSum(TreeNode root, long targetSum) { //外層遞歸,把每個節點都當作路徑起點if(root == null) return 0;int ret = rootSum(root, targetSum);ret += pathSum(root.left, targetSum);ret += pathSum(root.right, targetSum);return ret;}public int rootSum(TreeNode node, long targetSum) { //內層遞歸,//從當前節點往下探索路徑，看是否存在一條或多條路徑滿足 路徑和為 targetSumif(node == null) return 0;int ret = 0;if(node.val == targetSum) {ret++;}ret += rootSum(node.left, targetSum - node.val);ret += rootSum(node.right, targetSum - node.val);return ret;}
}

解法二：前綴和 + 回溯

class Solution {public int pathSum(TreeNode root, int targetSum) {// 首先創建一個hashmap// key: 前綴和, value: 該前綴和出現的次數Map<Long, Integer> prefixSumCount = new HashMap<>();prefixSumCount.put(0L, 1); //初始化前綴和為0的路徑數量return dfs(root, 0L, targetSum, prefixSumCount);}private int dfs(TreeNode node, long curSum, int targetSum, Map<Long, Integer> prefixSumCount) {if(node == null) return 0;curSum += node.val; //更新curSum//先查找有多少前綴和滿足 curSum - targetSumint count = prefixSumCount.getOrDefault(curSum - targetSum, 0);//然后更新prefixSumCountprefixSumCount.put(curSum, prefixSumCount.getOrDefault(curSum, 0) + 1);//遞歸左右子樹count += dfs(node.left, curSum, targetSum, prefixSumCount);count += dfs(node.right, curSum, targetSum, prefixSumCount);//回溯撤銷prefixSumCount.put(curSum, prefixSumCount.get(curSum) - 1);return count;}
}