力扣437力扣总和Ⅲ

给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):defpathSum(self,root,targetSum): :type root: Optional[TreeNode] :type targetSum: int :rtype: int prefix_map{0:1}# 前缀和为0的路径空路径出现一次self.count0self.targetSumtargetSumdefdfs(node,curr_sum):ifnotnode:returncurr_sumnode.val#curr_sum代表从根节点到当前节点的和#targetSum代表的就是目标和我们想要的是在前缀和里面寻找 curr_sum - prefix[A的父节点] targetSum# prefix[A的父节点] curr_sum - targetSum 记录这个值self.countprefix_map.get(curr_sum-targetSum,0)prefix_map[curr_sum]prefix_map.get(curr_sum,0)1dfs(node.left,curr_sum)dfs(node.right,curr_sum)prefix_map[curr_sum]-1dfs(root,0)returnself.count采用前缀和dfscurr_sum代表从根节点到当前节点的和targetSum代表的就是目标和我们想要的是在前缀和里面寻找 curr_sum - prefix[A的父节点] targetSum。然后计算次数