*LeetCode 437 – Python 3 (Week 4 – 01)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        #go through reach node. count the paths when the start node is that node.
        
        self.numOfPaths = 0
        
        self.dfs(root, sum)

        return self.numOfPaths
    
    def dfs(self, node, sum):
        if node is None:
            return 
        self.count(node, sum) 
        self.dfs(node.left, sum)
        self.dfs(node.right, sum)
        
    def count(self, node, sum):
        if node is None:
            return
        if node.val == sum:
            self.numOfPaths += 1       
        self.count(node.left, sum-node.val)
        self.count(node.right, sum-node.val)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.result = 0
        presum = {0:1}
        currentsum = 0
        
        self.dfs(root, sum, 0, presum)
        
        return self.result
    
    def dfs(self, root, sum, currentsum, presum):

        if root is None:
            return  
        
        currentsum += root.val
        needpresum = currentsum - sum
        
        self.result += presum.get(needpresum, 0)
        presum[currentsum] = presum.get(currentsum, 0) + 1
        
        self.dfs(root.left, sum, currentsum, presum)
        self.dfs(root.right, sum, currentsum, presum)
        # *********
        presum[currentsum] -= 1