Path Sum III
- 1 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- Complete Subarray Sum Equals K before this!!
- Probably my favorite problem of all time
- Literally uses the same concept from Subarray Sum Equals K but instead here you just need to remember to do it on a Depth-first Search and also backtrack
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
prefix_counts = defaultdict(lambda: 0)
prefix_counts[0] = 1
ans = 0
def dfs(node, cur_sum):
nonlocal ans
if node is None:
return
cur_sum += node.val
prefix_sum = cur_sum - targetSum
if prefix_sum in prefix_counts:
ans += prefix_counts[prefix_sum]
prefix_counts[cur_sum] += 1
dfs(node.left, cur_sum)
dfs(node.right, cur_sum)
prefix_counts[cur_sum] -= 1
cur_sum -= node.val
dfs(root, 0)
return ans