deepSWE.io

Path Sum III

TreesDFS

Problem Statement

Given the `root` of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values along the path equals `targetSum`. The path does not need to start or end at the root or a leaf, but it must go downwards.

Example

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Output: 3

The paths that sum to 8 are: 5 → 3, 5 → 2 → 1, and -3 → 11.

Algorithm Explanation

A brute-force approach would be to run a DFS from every node to find all paths that sum to the target. However, a more optimal solution uses a hash map to store prefix sums.

Algorithm Steps

Prefix Sum: As we traverse the tree, we'll calculate the prefix sum from the root to the current node.
Hash Map: We use a hash map to store the frequencies of prefix sums encountered so far.
DFS Traversal: We'll perform a DFS traversal. At each node, we update the current prefix sum. We then check if `currentSum - targetSum` exists in our hash map. If it does, it means there's a path ending at the current node with the desired sum.
Update Map: After checking, we add the current prefix sum to the hash map.
Backtrack: When we return from a recursive call, we must remove the current prefix sum from the hash map to ensure that we only consider paths going downwards.

Start

Starting DFS from the root.

Path Count: 0

Prefix Sum Map

0: 1

Path Sum III Solution


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # A map to store prefix sums and their frequencies
        self.prefix_sum_count = {0: 1}
        self.count = 0
        self.dfs(root, 0, targetSum)
        return self.count

    def dfs(self, node: Optional[TreeNode], current_sum: int, target_sum: int):
        if not node:
            return

        # Update the current path sum
        current_sum += node.val
        
        # Check if (current_sum - target_sum) exists in the map
        self.count += self.prefix_sum_count.get(current_sum - target_sum, 0)
        
        # Add the current sum to the map
        self.prefix_sum_count[current_sum] = self.prefix_sum_count.get(current_sum, 0) + 1
        
        # Continue the traversal
        self.dfs(node.left, current_sum, target_sum)
        self.dfs(node.right, current_sum, target_sum)
        
        # Backtrack: remove the current sum from the map
        self.prefix_sum_count[current_sum] -= 1