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 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def pathSumFrom(self, node, targetSum):
9 if not node:
10 return 0
11 return (node.val == targetSum) + self.pathSumFrom(node.left, targetSum - node.val) + self.pathSumFrom(node.right, targetSum - node.val)
12
13 def pathSum(self, root, targetSum):
14 if not root:
15 return 0
16 return self.pathSumFrom(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)
17The Python solution employs recursion to check all possible paths from each node. It is a direct translation of the algorithms from other languages into Python.
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.