437. 路径总和 III
已解答
中等
相关标签
相关企业
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def pathSum(self, root, targetSum):
"""
:type root: Optional[TreeNode]
:type targetSum: int
:rtype: int
"""
self.targetSum = targetSum
self.ret = 0
def dfs(tmp,current):
if tmp==None:
return
current += tmp.val
self.ret += self.prefix.get(current - self.targetSum ,0)
self.prefix[current] = self.prefix.get(current,0) + 1
dfs(tmp.left,current)
dfs(tmp.right,current)
self.prefix[current]-= 1
self.prefix={0:1}
dfs(root , 0)
return self.ret
这里我们需要的是一个非常牛逼的方法，也就是使用深度优先搜索，记录一个前缀和，然后在每次搜索的时候，之保留搜索这条路上的前缀和，这样子计算路径的时候只要把当前的路径前去任意一个前缀和的结果和target对上就行。
笨方法是直接遍历，深度搜索两次