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
The Java solution maintains a hashmap to track cumulative sums up to each node. The method helper explores the tree recursively, adjusting entries in the hashmap as nodes are visited and backtracking appropriately.