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.
1class TreeNode {
2 int val;
3 TreeNode left, right;
4 TreeNode(int x) { val = x; }
5}
6
7public class Solution {
8 private int dfs(TreeNode node, int sum) {
9 if (node == null) return 0;
10 return (node.val == sum ? 1 : 0) +
11 dfs(node.left, sum - node.val) +
12 dfs(node.right, sum - node.val);
13 }
14
15 public int pathSum(TreeNode root, int sum) {
16 if (root == null) return 0;
17 return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
18 }
19}
20This Java solution uses DFS to explore every path that ends at each node, recursively. The method dfs is called recursively on each node.
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.