LeetCode //C - 437. Path Sum III

437. Path Sum III

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

Constraints:

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

From: LeetCode
Link: 437. Path Sum III

---

Solution:

Ideas：

1. Struct TreeNode: This is a definition for a binary tree node which contains an integer value and pointers to the left and right child nodes.

2. DFS Function: This recursive function takes a node and the sums targetSum and currentSum as arguments, along with a pointer to an integer count that keeps track of the number of valid paths found.

   • As it traverses the tree, it adds the value of the current node to currentSum.
   • If currentSum equals targetSum, it increments the count.
   • It then recursively calls itself for the left and right children of the current node, passing along the updated currentSum.

3. pathSumFrom Function: This function is called for each node in the tree. It uses the dfs function to explore all paths that start from the current node.

   • It also recursively calls itself on the left and right children of the current node to ensure that paths starting from those nodes are also counted.

4. pathSum Function: This is the main function that initiates the path sum calculation. It starts the process by calling pathSumFrom for the root of the tree.

   • It maintains a count of the number of valid paths and returns this count as the result of the function.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void dfs(struct TreeNode* node, long long targetSum, long long currentSum, int* count) {
    if (!node) return;

    currentSum += node->val;
    if (currentSum == targetSum) {
        *count += 1;
    }

    dfs(node->left, targetSum, currentSum, count);
    dfs(node->right, targetSum, currentSum, count);
}

void pathSumFrom(struct TreeNode* node, long long targetSum, int* count) {
    if (!node) return;

    dfs(node, targetSum, 0, count);

    pathSumFrom(node->left, targetSum, count);
    pathSumFrom(node->right, targetSum, count);
}

int pathSum(struct TreeNode* root, int targetSum) {
    int count = 0;
    pathSumFrom(root, (long long)targetSum, &count);  // Explicitly cast targetSum to long long
    return count;
}