Sponsored
Sponsored
This approach uses a combination of DFS and path sum calculation. For each node, calculate the sum of all paths that end at the current node. This is achieved recursively
Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.
1#include <stdio.h>
2#include <stdbool.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int pathSumFrom(struct TreeNode* node, int targetSum) {
11 if (!node) return 0;
12 return (node->val == targetSum) +
13 pathSumFrom(node->left, targetSum - node->val) +
14 pathSumFrom(node->right, targetSum - node->val);
15}
16
17int pathSum(struct TreeNode* root, int targetSum) {
18 if (!root) return 0;
19 return pathSumFrom(root, targetSum) +
20 pathSum(root->left, targetSum) +
21 pathSum(root->right, targetSum);
22}
23This recursive solution calculates the number of paths that sum to the targetSum starting from each node. The function pathSumFrom checks both left and right paths recursively
This solution uses a hashmap called prefix to capture the number of ways to obtain each cumulative sum that ends at a node. When a node is visited, the difference between the current cumulative sum and the target is used to check for matching sums encountered earlier.