437. Path Sum III

Problem Description

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:
[5,3]
[5,2,1]
[-3,11]

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range [0, 1000]
• -10⁹ <= Node.val <= 10⁹
• -1000 <= targetSum <= 1000

Python Solution

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(node, curr_sum):
            if not node:
                return
            
            # Update current sum
            curr_sum += node.val
            
            # Add count of paths ending at current node
            self.count += h[curr_sum - targetSum]
            
            # Add current sum to hash map
            h[curr_sum] += 1
            
            # Recurse on children
            dfs(node.left, curr_sum)
            dfs(node.right, curr_sum)
            
            # Remove current sum from hash map (backtrack)
            h[curr_sum] -= 1
        
        self.count = 0
        h = defaultdict(int)
        h[0] = 1  # For paths starting from root
        dfs(root, 0)
        return self.count

Java Solution

class Solution {
    private int count = 0;
    private Map h = new HashMap<>();
    
    public int pathSum(TreeNode root, int targetSum) {
        h.put(0L, 1);  // For paths starting from root
        dfs(root, 0L, targetSum);
        return count;
    }
    
    private void dfs(TreeNode node, long currSum, int targetSum) {
        if (node == null) {
            return;
        }
        
        // Update current sum
        currSum += node.val;
        
        // Add count of paths ending at current node
        count += h.getOrDefault(currSum - targetSum, 0);
        
        // Add current sum to hash map
        h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        
        // Recurse on children
        dfs(node.left, currSum, targetSum);
        dfs(node.right, currSum, targetSum);
        
        // Remove current sum from hash map (backtrack)
        h.put(currSum, h.get(currSum) - 1);
    }
}

C++ Solution

class Solution {
private:
    int count = 0;
    unordered_map h;
    
    void dfs(TreeNode* node, long long currSum, int targetSum) {
        if (!node) {
            return;
        }
        
        // Update current sum
        currSum += node->val;
        
        // Add count of paths ending at current node
        count += h[currSum - targetSum];
        
        // Add current sum to hash map
        h[currSum]++;
        
        // Recurse on children
        dfs(node->left, currSum, targetSum);
        dfs(node->right, currSum, targetSum);
        
        // Remove current sum from hash map (backtrack)
        h[currSum]--;
    }
    
public:
    int pathSum(TreeNode* root, int targetSum) {
        h[0] = 1;  // For paths starting from root
        dfs(root, 0, targetSum);
        return count;
    }
};

JavaScript Solution

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
    let count = 0;
    const h = new Map();
    h.set(0, 1);  // For paths starting from root
    
    const dfs = (node, currSum) => {
        if (!node) {
            return;
        }
        
        // Update current sum
        currSum += node.val;
        
        // Add count of paths ending at current node
        count += h.get(currSum - targetSum) || 0;
        
        // Add current sum to hash map
        h.set(currSum, (h.get(currSum) || 0) + 1);
        
        // Recurse on children
        dfs(node.left, currSum);
        dfs(node.right, currSum);
        
        // Remove current sum from hash map (backtrack)
        h.set(currSum, h.get(currSum) - 1);
    };
    
    dfs(root, 0);
    return count;
};

C# Solution

public class Solution {
    private int count = 0;
    private Dictionary h = new Dictionary();
    
    public int PathSum(TreeNode root, int targetSum) {
        h[0] = 1;  // For paths starting from root
        DFS(root, 0L, targetSum);
        return count;
    }
    
    private void DFS(TreeNode node, long currSum, int targetSum) {
        if (node == null) {
            return;
        }
        
        // Update current sum
        currSum += node.val;
        
        // Add count of paths ending at current node
        if (h.ContainsKey(currSum - targetSum)) {
            count += h[currSum - targetSum];
        }
        
        // Add current sum to hash map
        if (!h.ContainsKey(currSum)) {
            h[currSum] = 0;
        }
        h[currSum]++;
        
        // Recurse on children
        DFS(node.left, currSum, targetSum);
        DFS(node.right, currSum, targetSum);
        
        // Remove current sum from hash map (backtrack)
        h[currSum]--;
    }
}