from utils.treeNode import TreeNode
from collections import defaultdict

class Solution:
    def get_paths_count(self, node, target):
        if not node:
            return 0
        sum_mapping = defaultdict(int)
        sum_mapping[0] = 1
        return self.helper(node, 0, target, sum_mapping)
    
    def helper(self, node, curr_sum, target, sum_mapping):
        if not node:
            return 0
        
        curr_sum += node.value

        result = sum_mapping[curr_sum - target]
        sum_mapping[curr_sum] += 1
        
        result += self.helper(node.left, curr_sum, target, sum_mapping)
        result += self.helper(node.right, curr_sum, target, sum_mapping)

        sum_mapping[curr_sum] -= 1
        return result
    

node1 = TreeNode(10)
node2 = TreeNode(5)
node3 = TreeNode(-3)
node4 = TreeNode(3)
node5 = TreeNode(2)
node6 = TreeNode(6)
node7 = TreeNode(11)
node8 = TreeNode(3)
node9 = TreeNode(-2)
node10 = TreeNode(1)

node1.left = node2
node1.right = node3

node2.left = node4
node2.right = node5

node4.left = node8
node4.right = node9

node5.left = node10

node3.right = node7
# node6.left = node7

print(node1)
solution = Solution()
print(solution.get_paths_count(node1, 8))