Path Sum III - Python Solution

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.