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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6function pathSum(root, targetSum) {
7 if (!root) return 0;
8
9 function pathSumFrom(node, target) {
10 if (!node) return 0;
11 return (node.val === target ? 1 : 0) +
12 pathSumFrom(node.left, target - node.val) +
13 pathSumFrom(node.right, target - node.val);
14 }
15
16 return pathSumFrom(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
17}
18JavaScript implementation that uses recursion to find all paths that sum to the target, analogous to other language solutions with some JavaScript-specific adaptations.
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.