HTMLify

class Solution:
    def countAllPaths(self, root, k):
        prefix_sums = {0: 1}
        
        def dfs(node, current_sum):
            if not node:
                return 0
            
            current_sum += node.data
            
            count = prefix_sums.get(current_sum - k, 0)
            
            prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
            
            count += dfs(node.left, current_sum)
            count += dfs(node.right, current_sum)
            
            prefix_sums[current_sum] -= 1
            
            return count
            
        return dfs(root, 0)