国内免费的建网站平台_成都网站建设服务_b2b平台网站_雅诗兰黛网络营销策划书

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;}
}