class Tree(object):
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right
tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))
def find_paths(root, required_sum):
allPaths = []
def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
if currentNode is None:
return
# add the current node to the path
currentPath.append(currentNode.val)
# if the current node is a leaf and its value is equal to required_sum, save the current path
if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub-tree
find_paths_recursive(currentNode.left, required_sum -
currentNode.val, currentPath, allPaths)
# traverse the right sub-tree
find_paths_recursive(currentNode.right, required_sum -
currentNode.val, currentPath, allPaths)
# remove the current node from the path to backtrack,
# we need to remove the current node while we are going up the recursive call stack.
del currentPath[-1]
find_paths_recursive(root, required_sum, [], allPaths)
return allPaths
find_paths(tx, 5)
Comments