Path Sum III

class Solution {
    int pathsFound = 0;
    int desiredSum;
    HashMap<Long, Integer> prefixSumCount = new HashMap<>();

    public void traverse(TreeNode currentNode, long currentSum) {
        if (currentNode == null)
            return;

        currentSum += currentNode.val;

        if (currentSum == desiredSum)
            pathsFound++;

        pathsFound += prefixSumCount.getOrDefault(currentSum - desiredSum, 0);

        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);

        traverse(currentNode.left, currentSum);
        traverse(currentNode.right, currentSum);

        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);
    }

    public int pathSum(TreeNode root, int target) {
        desiredSum = target;
        traverse(root, 0L);
        return pathsFound;
    }
}

Discover how to solve the Path Sum III problem using Java. The provided code efficiently counts the number of paths that sum to a given target by leveraging a HashMap to track prefixes of sums throughout a tree traversal.

In this Java program, initiate the variable pathsFound to store the count of paths that equal the target value. Define desiredSum to hold the target sum against which to compare path sums. Use a HashMap, prefixSumCount, to remember the count of prefix sums encountered during the tree traversal.

Detailed implementation steps are as follows:

1. Implement the traverse method to perform a recursive depth-first search (DFS) through the tree:

   • Skip processing if the currentNode is null.
   • Update currentSum by adding the current node’s value.
   • Check if currentSum matches desiredSum. If it does, increment pathsFound.
   • Increment pathsFound by the number of times the difference currentSum - desiredSum has been seen (obtained from prefixSumCount).
   • Update prefixSumCount to include the current currentSum, or increment its count if already present.
   • Recursively call traverse for the left and the right children of the current node.
   • After returning from recursion, adjust prefixSumCount to reflect moving out of the subtree of the current node.

2. Implement the pathSum method to serve as an entry point for the algorithm:

   • It sets the desiredSum based on the given target.
   • It starts the traversal from the root of the tree with an initial currentSum of 0.
   • Returns pathsFound after traversal completes, representing the total number of valid paths found.

This approach uses prefix sums optimally with a map to reduce the time complexity typically associated with path sum computations in trees, achieving efficiency not only in terms of runtime but also in implementation clarity. With this method, efficiently count paths in large trees corresponding to a given sum.

class Solution:
    def countPaths(self, node_root: TreeNode, target_sum: int) -> int:
        def explore(node: TreeNode, accumulated_sum) -> None:
            nonlocal path_count
            if not node:
                return 

            # Update current sum with node's value
            accumulated_sum += node.val
            
            # Check if current sum equals target_sum
            if accumulated_sum == target_sum:
                path_count += 1
            
            # Increment path count by number of occurrences of (accumulated_sum - target_sum)
            path_count += record[accumulated_sum - target_sum]
            
            # Store current accumulated_sum in map
            record[accumulated_sum] += 1
            
            # Explore left and right children
            explore(node.left, accumulated_sum)
            explore(node.right, accumulated_sum)
            
            # Once returning from recursion, decrement the map's count for accumulated_sum
            record[accumulated_sum] -= 1
            
        path_count, target_sum = 0, sum
        record = defaultdict(int)
        explore(node_root, 0)
        return path_count

The given Python code defines a class Solution with a method countPaths that calculates the number of paths in a binary tree such that the sum of the node values in the path equals a target sum. Here is a breakdown of the method:

• Initial Setup: The method initializes variables path_count to track the total number of valid paths and a record dictionary using defaultdict(int) to store cumulative sums encountered during the tree traversal.

• Recursive Function explore: This nested function traverses the tree starting from the given node_root.

  • If the current node is None, the recursion ends.
  • Updates the current path's accumulated sum by adding the current node's value.
  • If the accumulated sum equals the target_sum, increments path_count.
  • Also checks if there's a previous path ending where the accumulated sum minus the target_sum exists in record, indicating that starting from that point to the current node makes a valid path. Updates path_count accordingly.
  • Adds the current accumulated sum to the record to signify this sum is reached up to this node.
  • Recursively calls itself for left and right child nodes.
  • When backtracking from recursion (after exploring both children), decreases the count for the current accumulated sum in record.

• End of Exploration: After fully exploring the tree, the final path_count is returned, which represents the number of paths found satisfying the sum condition.

The use of dictionary record optimizes the solution by allowing fast checks and updates on the sums encountered across different paths without recalculating from the root for each node. This approach combines depth-first search with a hashmap, effectively handling the cases where multiple paths might sum up to the target starting from different nodes.