1def pathSum(root, target):
2 answer = 0
3 prefix_count = {0: 1} # Base case: empty path
4
5 def dfs(node, curr_sum):
6 nonlocal answer
7
8 if not node:
9 return
10
11 # Count paths ending at this node
12 curr_sum += node.val
13 needed = curr_sum - target
14 paths_found = prefix_count.get(needed, 0)
15 answer += paths_found
16
17 # Add current sum to prefix map
18 prefix_count[curr_sum] = prefix_count.get(curr_sum, 0) + 1
19
20 # Recurse into left and right
21 dfs(node.left, curr_sum)
22 dfs(node.right, curr_sum)
23
24 # Backtrack: remove current sum
25 prefix_count[curr_sum] -= 1
26
27 dfs(root, 0)
28 return answer| Variable | Value |
|---|---|
root | "Node(1)" |
target | 3 |
answer | - |
prefix_count | - |
| Depth | Function Call |
|---|---|
| 1 | pathSum(Node(1), 3) |
1def pathSum(root, target):
2 answer = 0
3 prefix_count = {0: 1} # Base case: empty path
4
5 def dfs(node, curr_sum):
6 nonlocal answer
7
8 if not node:
9 return
10
11 # Count paths ending at this node
12 curr_sum += node.val
13 needed = curr_sum - target
14 paths_found = prefix_count.get(needed, 0)
15 answer += paths_found
16
17 # Add current sum to prefix map
18 prefix_count[curr_sum] = prefix_count.get(curr_sum, 0) + 1
19
20 # Recurse into left and right
21 dfs(node.left, curr_sum)
22 dfs(node.right, curr_sum)
23
24 # Backtrack: remove current sum
25 prefix_count[curr_sum] -= 1
26
27 dfs(root, 0)
28 return answer