Path Sum III - Java Solution

1. Introduction

This blog post examines the "Path Sum III" problem, a notable challenge in binary tree algorithms. The problem involves finding the number of paths in a binary tree where the sum of the values along the path equals a given target sum. This problem is significant for its application in computational problems involving tree data structures, particularly in scenarios where path calculations are crucial.

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 must travel downwards (from parent nodes to child nodes) but does not need to start at the root or end at a leaf.

2. Solution Steps

1. Use a recursive approach to explore all possible paths in the tree.

2. For each node, consider paths starting from it and also include it in paths from its ancestors.

3. Keep a running sum of node values along each path and compare it with targetSum.

4. Increment a counter every time a path sum equals targetSum.

5. Return the total count of such paths.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class PathSumIII {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        root.right.right = new TreeNode(11);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right.right = new TreeNode(1);

        int targetSum = 8;
        System.out.println(pathSum(root, targetSum)); // Test the function
    }

    // Function to count the paths that sum to a target value
    public static int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return pathsFromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    // Helper function to count paths starting from the current node
    private static int pathsFromNode(TreeNode node, int targetSum) {
        if (node == null) return 0;

        int count = 0;
        if (node.val == targetSum) count++;

        count += pathsFromNode(node.left, targetSum - node.val);
        count += pathsFromNode(node.right, targetSum - node.val);
        return count;
    }
}

Output:

3

Explanation:

1. pathSum: This function is the entry point for finding the number of paths that sum to targetSum. It counts paths starting from the current node and recurses on the left and right children to count paths starting from them.

2. pathsFromNode: A helper function that calculates the number of paths starting from a particular node that sum up to the target. It recursively explores all paths downward from the current node.

3. The function aggregates the count of valid paths starting from the current node and its left and right subtrees.

4. The main function calls pathSum with the root node and targetSum, returning the total count of paths summing to the target.

5. The solution employs a recursive approach, exploring each potential path in the tree and keeping track of the sum along the way, efficiently counting the paths that meet the criteria.