LeetCode 437.路径总和 III(树上玩前缀+回溯)

本文主要是介绍LeetCode 437.路径总和 III(树上玩前缀+回溯)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

本题这里有两种解法：

类似暴力，可以参照113. 路径总和 II这题，只不过多了遍历整棵树这个过程而已，这种解法多了很多重复的计算
前缀和，本篇文章主要讲解这种解法

第一眼看到这个题目时，想的就是暴力或则前缀和来解决。暴力的话，感觉太low了，可是前缀和我也只做过在数组中的啊，这nm前缀跑树上来，我这咋写？？怎么定义前缀数组？？麻了呀！！！

算了，看题解！！！

这一看，这好像似曾相识啊，跟以前写的那题思想一样啊！
560. 和为 K 的子数组

主要思路为：
我们用HashMap时，将前缀和保存为Key，前缀和出现的次数保存为value
开始遍历后，我们计算前缀和preSum，如果preSum-k存在时，说明中间这个子数组则为答案。下面这个图可以很好的解释；
否则的话我们将preSum放入HashMap中
在这里插入图片描述

class Solution {public int pathSum(TreeNode root, int targetSum) {Map<Integer,Integer> map=new HashMap<>();//这里必须先把0放进去；//不放的话，比如说只有一个节点3，目标和也为3，这样的话答案就为0.map.put(0,1);return prefix(root,targetSum,map,0);}private int prefix(TreeNode root, int targetSum, Map<Integer, Integer> map,int pre) {if(root==null) return 0;//计算当前节点的前缀和pre=pre+root.val;int res=0;//获取到这个节点，满足条件的个数res=map.getOrDefault(pre-targetSum,0);//将该前缀和写入map中map.put(pre,map.getOrDefault(pre,0)+1);//获取左子树符合条件的个数res+=prefix(root.left,targetSum,map,pre);//获取右子树符合条件的个数res+=prefix(root.right,targetSum,map,pre);//回溯回去，必须去掉当前这个节点的前缀和map.put(pre,map.get(pre)-1);return res;}
}