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)
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter