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.
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.