中山最好的网站建设公司,移动端英文简称,建外贸网站用什么主机,班徽logo设计生成器题目链接
路径总和 III
题目描述 注意点
二叉树的节点个数的范围是 [0,1000]求该二叉树里节点值之和等于 targetSum 的 路径 的数目
解答思路
可根据前缀和的思路解决本题#xff0c;前缀和表示从根节点开始#xff0c;往左或往右组成的路径和#xff0c;统计从根节点开…题目链接
路径总和 III
题目描述 注意点
二叉树的节点个数的范围是 [0,1000]求该二叉树里节点值之和等于 targetSum 的 路径 的数目
解答思路
可根据前缀和的思路解决本题前缀和表示从根节点开始往左或往右组成的路径和统计从根节点开始的所有的前缀和以及前缀和出现的次数当遍历到任意一个节点时可根据加上该节点值形成的当前值与目标值的差值也就是currSum - targetSum在前缀和中出现的次数推出加上该节点时路径和为targetSum的路径数因为路径方向必须是向下的只能从父节点到子节点所以父节点的前缀和只会影响其对应的左右子树所以在前缀和映射中加上当前节点后递归其左右子树进行相同的操作且在递归完左右子树后需要将前缀和映射恢复防止左右两个子树互相造成影响
代码
class Solution {public int pathSum(TreeNode root, int targetSum) {// key为前缀和的值value为前缀和为key时的路径数量MapLong, Integer map new HashMap();// 没有任何节点时前缀和为0保证根节点为targetSum也能正确统计路径数map.put(0L, 1);return recursionPathSum(root, map, 0L, targetSum);}public int recursionPathSum(TreeNode root, MapLong, Integer map, Long currSum, int targetSum) {if (root null) {return 0;}int res 0;currSum root.val;// 根据前一层的前缀和的值推出加上此节点时结果为targetSum的路径数res map.getOrDefault(currSum - targetSum, 0);// 增加新的前缀和映射进入下一层对左右子树进行递归map.put(currSum, map.getOrDefault(currSum, 0) 1);res recursionPathSum(root.left, map, currSum, targetSum);res recursionPathSum(root.right, map, currSum, targetSum);// 恢复状态防止左右子树的前缀和各自产生影响map.put(currSum, map.get(currSum) - 1);return res;}
}关键点
前缀和的思想父节点的前缀和映射只会对其下方的子树判断路径总和有影响而不会对同层或更高层的节点产生影响所以在对子树递归后还要将该节点的前缀和映射进行恢复
