437. 路径总和 III

class Solution(object):
    def pathSum(self, root, target):
        """
        :type root: TreeNode
        :type sumt: int
        :rtype: int
        """
        self.count = 0
        myDict = {0: 1}

        def dfs(p, target, pathSum, myDict):
            if p:
                pathSum += p.val
                self.count += myDict.get(pathSum - target, 0)
                myDict[pathSum] = myDict.get(pathSum, 0) + 1
                dfs(p.left, target, pathSum, myDict)
                dfs(p.right, target, pathSum, myDict)
                myDict[pathSum] -= 1
        dfs(root, target, 0, myDict)
        return self.count