path sum iii

← 🏠

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

 1class 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