LeetCode437-路径总和III，DFS+map，Golang
437. 路径总和 III
题意：
给定一颗二叉树，和一个目标总和targetsum，要求树上有多少条路径的节点和等于targetsum，其中每条路径不需要从根节点开始，也不需要到叶子节点结束，但必须是自顶向下的，不能出现同层节点。
思路：
利用深度优先搜索进行求解，搜索过程中，用一个map来保存当前搜索过程中，所有和数出现的次数，用 路径累积和-目标和 出现的次数更新答案。
代码：
golang
func pathSum(root *TreeNode, targetSum int) int { mp:=make(map[int64]int) accumulate_sum:=int64(0) ans:=0 var dfs func(rt *TreeNode) dfs=func(rt*TreeNode){ if rt==nil{ return } accumulate_sum+=int64(rt.Val) if mp[accumulate_sum-int64(targetSum)]>0{ ans+=mp[accumulate_sum-int64(targetSum)] } mp[accumulate_sum]++ dfs(rt.Left) dfs(rt.Right) mp[accumulate_sum]-- accumulate_sum-=int64(rt.Val) } mp[0]=1 dfs(root) return ans}CPP
class Solution {public: unordered_mapmp; int dfs(TreeNode*now, long long cur, int targetSum){ if(!now) return 0; int res=0; cur+=now->val; if(mp.count(cur-targetSum)) res+=mp[cur-targetSum]; mp[cur]++; res+=dfs(now->right,cur,targetSum); res+=dfs(now->left,cur,targetSum); mp[cur]--; return res; } int pathSum(TreeNode* root, int targetSum) { mp[0]=1; return dfs(root,0,targetSum); }};