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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 private int PathSumFrom(TreeNode node, int targetSum) {
10 if (node == null) return 0;
11 return (node.val == targetSum ? 1 : 0) +
12 PathSumFrom(node.left, targetSum - node.val) +
13 PathSumFrom(node.right, targetSum - node.val);
14 }
15
16 public int PathSum(TreeNode root, int targetSum) {
17 if (root == null) return 0;
18 return PathSumFrom(root, targetSum) + PathSum(root.left, targetSum) + PathSum(root.right, targetSum);
19 }
20}
21The C# solution utilizes recursion to check paths in each subtree and sum up the results across the tree. It's similar to C++ and Java implementations, catered to C# syntax.
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.