# 1. Introduction

"Path Sum III" is an intriguing problem that involves traversing a binary tree to find the number of paths that sum up to a given target. Unlike typical path problems, these paths do not need to start at the root or end at a leaf but must follow a top-down approach. This problem tests understanding of depth-first search and recursive algorithms in tree data structures.

## Problem

Given the root of a binary tree and an integer *targetSum*, the task is to return the number of paths where the sum of the values along the path equals *targetSum*. The path can start and end at any node in the tree but must go downwards, traveling only from parent nodes to child nodes.

# 2. Solution Steps

1. Traverse the tree using depth-first search.

2. At each node, check all possible paths and count those that sum up to the target.

3. Implement a recursive function to calculate the sum of paths starting from a given node.

4. Aggregate the counts of valid paths from each node in the tree.

5. Return the total number of paths that meet the target sum.

# 3. Code Program

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pathSum(root, targetSum):
def countPaths(node, currentSum):
if not node:
return 0
currentSum += node.val
pathCount = cache[currentSum - targetSum]
cache[currentSum] += 1
pathCount += countPaths(node.left, currentSum)
pathCount += countPaths(node.right, currentSum)
cache[currentSum] -= 1
return pathCount
cache = defaultdict(int)
cache[0] = 1
return countPaths(root, 0)
# Example Usage
root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(2, None, TreeNode(1))), TreeNode(-3, None, TreeNode(11)))
print(pathSum(root, 8))
```

### Output:

3

### Explanation:

**1. Recursive Depth-First Search**: The *countPaths* function explores each node, calculating the sum of all paths from the node downwards.

**2. Path Counting**: It counts the number of paths that sum up to *targetSum* starting from the current node.

**3. Cumulative Sums**: The function uses a cache to keep track of the number of times each sum has occurred so far during the traversal.

**4. Path Calculation**: By subtracting the target sum from the current cumulative sum, we determine if a valid path ending at the current node exists.

**5. Total Paths**: The function aggregates the valid path counts from each node, resulting in the total number of paths equaling *targetSum*.

## Comments

## Post a Comment