Cleaner solution with a slight optimization.
I am not sure but with this solution I am seeing an average case of an O(n) time complexity and to be specific O(n + n) as we only need to iterate at each node only if we have gone past the required sum.
Worst case scenario is we have a large target sum of say 100 and in one path we have added all numbers from root to leaf - 1 and it adds to say 95 and we then add the number at the leaf of 120 meaning we would need to iterate once through all the previous nodes to remove them.
4
/
35
/
6
/
5
/
15
/
20
/
10
/
120
def count_paths(root, S):
return count_paths_recursive(root, S, [], 0)
def count_paths_recursive(node, sum, current_path, start_index):
if node is None:
return 0
current_path.append(node.val)
path_count = 0
sum -= node.val
# We have found a path including our current node so add to the path_count
if sum == 0:
path_count += 1
# Added too many nodes so lets try and subtruct from the beginning
elif sum < 0:
while start_index < len(current_path) and sum < 0:
sum += current_path[start_index]
start_index += 1
# Check again to see if we have a path after deducting some numbers
if sum == 0:
path_count += 1
# Continue to children to see if any more paths exist
path_count += count_paths_recursive(node.left, sum, current_path, start_index)
path_count += count_paths_recursive(node.right, sum, current_path, start_index)
# Backtrack after popping each frame off the call stack
# as current_path is a list(reference type) and we have mutated it meaning
# it will affect nodes further up the tree
del current_path[-1]
return path_count
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5658962204557312