path sum iii

🏠

This is an extremely easy question to answer if you've first covered subarray sum equals k.

 1 class Solution:
 2     def pathSum(self, root: TreeNode, k: int) -> int:
 3         def dfs(n, acc, counter):
 4             if n:
 5                 acc += n.val
 6                 self.n += counter[(acc - k)] if (acc - k) in counter else 0
 7                 counter[acc] = 1 + (counter[acc] if acc in counter else 0)
 8                 dfs(n.left, acc, counter.copy())
 9                 dfs(n.right, acc, counter.copy())
10         self.n = 0
11         dfs(root, 0, {0:1})
12         return self.n