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 <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11};
12
13class Solution {
14public:
15 int dfs(TreeNode* node, int sum) {
16 if (!node) return 0;
17 return (node->val == sum) + dfs(node->left, sum - node->val) + dfs(node->right, sum - node->val);
18 }
19 int pathSum(TreeNode* root, int sum) {
20 if (!root) return 0;
21 return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
22 }
23};The C++ solution uses depth-first search from each node, checking all downward paths. This is a direct translation from the C solution but takes advantage of C++ class structures.
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.