Tree: Depth-First Search - Path Sum II (All Root-to-Leaf Paths)
Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list?
Tree structure:
5
/ \
4 8
/ / \
11 13 4
Target sum: 7
def pathSum(root, targetSum):
if not root:
return []
res = []
stack = [(root, [root.val], root.val)]
while stack:
node, path, current_sum = stack.pop()
if not node.left and not node.right:
if current_sum == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
return res