This problem can be solved using Depth-First Search (DFS) and prefix sum. Here are the steps:

1. Initialize a global variable `count` to keep track of the number of paths that sum to `K`.

2. Create a recursive function `dfs(node, prefixSum)`. This function will perform a depth-first search on the binary tree, keeping track of the sum of the path from the root to the current node.

3. In the `dfs` function, if the node is null, return.

4. Add the value of the current node to `prefixSum`.

5. Check if there are any paths that end at the current node and sum to `K`. This can be done by checking if `prefixSum - K` exists in the prefix sum map. If it does, add the value of `prefixSum - K` in the map to `count`.

6. Add `prefixSum` to the prefix sum map.

7. Recursively call `dfs` on the left and right children of the current node.

8. After visiting all children of the current node, remove `prefixSum` from the map to backtrack.

9. After the DFS is done, return `count` modulo 109+7.

Here is a Python code snippet that implements these steps:

```python
from collections import defaultdict

MOD = 10**9 + 7
count = 0
prefixSumCount = defaultdict(int)

def dfs(node, prefixSum):
global count
if not node:
return
prefixSum += node.val
count += prefixSumCount[prefixSum - K]
prefixSumCount[prefixSum] += 1
dfs(node.left, prefixSum)
dfs(node.right, prefixSum)
prefixSumCount[prefixSum] -= 1

dfs(root, 0)
return count % MOD
```

In this code, `root` is the root of the binary tree and `K` is the target sum. The `dfs` function is called initially with the root of the tree and a prefix sum of 0.

Question

This problem can be solved using Depth-First Search (DFS) and prefix sum. Here are the steps:

1. Initialize a global variable `count` to keep track of the number of paths that sum to `K`.

2. Create a recursive function `dfs(node, prefixSum)`. This function will perform a depth-first search on the binary tree, keeping track of the sum of the path from the root to the current node.

3. In the `dfs` function, if the node is null, return.

4. Add the value of the current node to `prefixSum`.

5. Check if there are any paths that end at the current node and sum to `K`. This can be done by checking if `prefixSum - K` exists in the prefix sum map. If it does, add the value of `prefixSum - K` in the map to `count`.

6. Add `prefixSum` to the prefix sum map.

7. Recursively call `dfs` on the left and right children of the current node.

8. After visiting all children of the current node, remove `prefixSum` from the map to backtrack.

9. After the DFS is done, return `count` modulo 109+7.

Here is a Python code snippet that implements these steps:

```python
from collections import defaultdict

MOD = 10**9 + 7
count = 0
prefixSumCount = defaultdict(int)

def dfs(node, prefixSum):
    global count
    if not node:
        return
    prefixSum += node.val
    count += prefixSumCount[prefixSum - K]
    prefixSumCount[prefixSum] += 1
    dfs(node.left, prefixSum)
    dfs(node.right, prefixSum)
    prefixSumCount[prefixSum] -= 1

dfs(root, 0)
return count % MOD
```

In this code, `root` is the root of the binary tree and `K` is the target sum. The `dfs` function is called initially with the root of the tree and a prefix sum of 0.

Knowee AI · Accepted Answer