437. Path Sum III Medium

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 (i.e., traveling only from parent nodes to child nodes).

Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Approach

Input: The root node of a binary tree root, and an integer targetSum

Output: Return the number of paths in this binary tree where the sum of node values equals targetSum

This problem is suitable to be solved using Top-down DFS + Prefix Sum + Hash Table.

• Preorder DFS traversal, maintaining the current prefix sum curr.
• Use a hash table cnt to record "the number of times a certain prefix sum has appeared". Initialize cnt[0] = 1 (empty path prefix).
• For each node:
  1. curr += node.val
  2. Add cnt[curr - targetSum] to the answer (these are the valid paths ending at the current node)
  3. cnt[curr]++
  4. Recursively traverse left and right subtrees
  5. Backtrack: cnt[curr]-- (withdraw the current contribution before returning to the parent node)

Implementation

python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # Use a dictionary to record the prefix sum and its frequency of occurrence, sums[total] represents the number of paths with prefix sum total
        sums = defaultdict(int)
        sums[0] = 1  # Initialization, meaning there is a path with prefix sum 0 starting from the root node
        
        # Depth First Search, total represents the total sum of the current path
        def dfs(root, total):
            count = 0
            if root:  # Recursion termination condition: return 0 when the current node is null
                # Update current path sum
                total += root.val

                # If there is a path with prefix sum equal to total - targetSum, it means a path with sum targetSum is found
                count = sums[total - targetSum]

                # Add the current path sum to sums, indicating it appeared once
                sums[total] += 1
                
                # Recursively calculate the path sum in the left and right subtrees
                count += dfs(root.left, total) + dfs(root.right, total)
                
                # Backtrack: after traversing the left and right subtrees of the current node, remove the record of the current path sum to avoid affecting other paths
                sums[total] -= 1
            return count
        
        # Start from the root node, initial path sum is 0
        return dfs(root, 0)

javascript

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function (root, targetSum) {
    const cnt = new Map();
    cnt.set(0, 1); // Empty prefix

    const dfs = (node, curr) => {
        if (!node) return 0;

        curr += node.val;
        // The number of paths ending at the current node and summing to targetSum
        const need = curr - targetSum;
        let res = cnt.get(need) || 0;

        // Record the current prefix sum before entering subtrees
        cnt.set(curr, (cnt.get(curr) || 0) + 1);
        res += dfs(node.left, curr);
        res += dfs(node.right, curr);
        // Backtrack
        cnt.set(curr, cnt.get(curr) - 1);

        return res;
    };

    return dfs(root, 0);
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

Links

437. Path Sum III (English)

437. 路径总和 III (Chinese)