# 437. Path Sum III

# Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
# The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

# Example 1:
# Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
# Output: 3
# Explanation: The paths that sum to 8 are shown.

# Example 2:
# Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
# Output: 3

# 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):
        dic = {0: 1}

        def dfs(root, currSum, targetSum):
            if not root:
                return 0
            currSum += root.val
            rs = 0
            if (currSum - targetSum) in dic:
                rs += dic[currSum - targetSum]

            if currSum in dic:
                dic[currSum] += 1
            else:
                dic[currSum] = 1

            rs += dfs(root.left, currSum, targetSum)
            rs += dfs(root.right, currSum, targetSum)
            dic[currSum] -= 1

            return rs

        return dfs(root, 0, targetSum)
