核心内容摘要
突破iOS激活锁终极方案：AppleRa1n实战指南
思路前缀和解法利用前缀和求节点值之和等于targetSum的路径的数目满足路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。
前缀和定义
定义一个节点的前缀和就是该节点到根之间的路径和。
举例如下图所示。
1节点4的前缀和为1 2 4 7。
2节点8的前缀和为1 2 4 8 15。
3节点9的前缀和为1 2 5 9 17。
本题中前缀和的作用两节点间的路径和即为两节点的前缀和之差。
举例1如下图所示假如题目给定数值为5节点1的前缀和为1节点3的前缀和为1 2 3 6。
2prefix(
- prefix(
5。
3所以节点1到节点3之间有一条符合要求的路径
。
利用前缀和简化问题我们只需要遍历整棵树一次记录每个节点的前缀和并查询该节点的祖先节点中符合条件的个数将这个数量加到最终结果上。
HashMap存储数据key存储前缀和value是该前缀和的节点数量记录数量是因为有出现重复路径的可能。
举例如下图所示改图中前缀和为1的节点有两个分别是0和1所以路径和为2的路径数就有两条分别是
和2。
.
恢复状态的意义
题目要求路径方向必须是向下的即只能从父节点到子节点。
当计算两个节点的前缀和的差值时其中一个节点必须是另一个节点的祖先节点。
换句话说当我们把一个节点的前缀和信息更新到map里时它应当只对其子节点们生效。
举例下图中有两个值为2的节点AB。
1当遍历到最右方的节点6时对于它来说此时的前缀和为2的节点只该有B因为A并不是节点6的祖先节点。
2如果不做状态恢复的话当遍历右子树时左子树中A的信息仍会保留在map中那么此时节点6就会认为AB都是可追溯到的节点从而产生错误。
状态恢复代码的作用在遍历完一个节点的所有子节点后将其从map中除去。
核心思想寻找从根节点到当前节点的路径上是否存在某个前缀和curSum - target。
如果存在则说明从那个前缀和对应的节点到当前节点的路径和正好等于target。
即curSum - (curSum - target) target。
附代码class Solution { MapLong,Integer prefixMap; int target; public int pathSum(TreeNode root, int targetSum) { prefixMap new HashMap(); target targetSum; // key表示前缀和value表示前缀和为这个值的路径的数量。
// 初始化表示空路径的前缀和为0出现了1次为了处理从根节点开始的路径 prefixMap.put(0L,
; return recur(root,0L); } // recur函数用于遍历二叉树对于每个节点记录前缀和的同时返回当前找到和为target的路径的数量 // curSum表示node节点之前的前缀和 private int recur(TreeNode node,Long curSum){ if(node null){ return 0; } int res 0; // 记录路径数量 curSum node.val; // 根节点到当前节点的路径和 // 如果curSum - target在prefixMap中存在则说明存在某个节点到当前节点的路径和等于target // curSum - (curSum - target) target // 比如target 8如果之前存在前缀和 5且当前前缀和 13那么13 - 5 8说明从那个节点到当前节点的路径和为8 res prefixMap.getOrDefault(curSum - target,
; // 把当前节点的前缀和也加入到哈希表中value加1 prefixMap.put(curSum,prefixMap.getOrDefault(curSum,
0)
; // 递归处理子树 int left recur(node.left,curSum); int right recur(node.right,curSum); res res left right; // 所有找到的路径数量总和即为总的路径数量 // 恢复状态 prefixMap.put(curSum,prefixMap.get(curSum) -
; // 当前节点处理完后要返回到父节点当前节点的前缀和不应该影响其他分支的统计。
因此在遍历完一个节点的所有子节点后将其从map中除去 return res; } }