Path Sum III: Count All Paths That Sum to Target

The problem asks us to find all downward paths in a binary tree where the sum of node values equals a target value. We don’t need paths from root to leaf—we just need paths that go down from parent to child nodes.

Core Idea

The key insight is recursive counting. Since we don’t need root-to-leaf paths, we can treat every node as a potential starting point. By breaking down the problem into subproblems, we transform it into: for each starting node, recursively find paths that sum to our target.

We use two nested recursions to accumulate results. The first recursion chooses starting points (every node in the tree). The second recursion, from each starting point, counts valid paths downward.

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        // DFS counts from fixed start point, pathSum changes the start location
        return DFS(root, 0, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }
private:
    int DFS(TreeNode* root, int sum, int &target) {
        if (!root) return 0;
        int curSum = sum + root->val;
        // Equal means 1 match, then search left and right subtrees recursively
        return (curSum == target) + DFS(root->left, curSum, target) + DFS(root->right, curSum, target);
    }
};

What I Learned

This problem teaches recursive counting and problem decomposition. The technique of using nested recursion—once for choosing starting points and once for counting paths from each start—is powerful for tree problems with multiple valid starting locations.

#tree