要求
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
思路
前缀和:该节点到根之间的路径和,也就是说到达当前元素的路径上,之前所有元素的和。
节点8的前缀和:1 + 2 + 4 + 8 = 15
节点9的前缀和:1 + 2 + 5 + 9 = 17
1
/ \
2 3
/ \ \
4 5 6
/ \ \
7 8 9
题目要求的是找出路径和等于给定数值的路径总数, 而:两节点间的路径和 = 两节点的前缀和之差
1
/
2
/
3
/
4
假如题目给定数值为5
节点1的前缀和为: 1
节点3的前缀和为: 1 + 2 + 3 = 6
prefix(3) - prefix(1) == 5
所以 节点1 到 节点3 之间有一条符合要求的路径( 2 --> 3 )
HashMap存的是什么?
HashMap的key是前缀和, value是该前缀和的节点数量,记录数量是因为有出现复数路径的可能。
恢复状态的意义
由于题目要求:路径方向必须是向下的(只能从父节点到子节点)
当我们把一个节点的前缀和信息更新到map里时,它应当只对其子节点们有效。
状态恢复代码的作用就是: 在遍历完一个节点的所有子节点后,将其从map中除去。
public class LeetCode437 {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0L,1);
return recursionPathSum(root,prefixSumCount,targetSum,0L);
}
private int recursionPathSum(TreeNode node, Map<Long, Integer> prefixSumCount, int target, long currSum) {
if (node == null) {
return 0;
}
int res = 0;
currSum += node.val;
res += prefixSumCount.getOrDefault(currSum-target,0);
prefixSumCount.put(currSum,prefixSumCount.getOrDefault(currSum,0)+1);
res += recursionPathSum(node.left,prefixSumCount,target,currSum);
res += recursionPathSum(node.right,prefixSumCount,target,currSum);
prefixSumCount.put(currSum,prefixSumCount.get(currSum) - 1) ;
return res;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)