We traverse the tree using DFS. At each node, we add it to the current path and subtract its value from the target. If we reach a leaf with target == 0, we save the path. We backtrack by removing the node.
- DFS from the root, maintaining the current path and remaining sum.
- At each node, add it to the path and subtract from remaining.
- If it's a leaf and remaining is 0, save the path.
- Recurse on left and right children.
- Backtrack by removing the node from the path.
- Time Complexity: O(N^2) in worst case (skewed tree).
- Space Complexity: O(N).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def path_sum(root, target_sum):
result = []
def dfs(node, remaining, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
result.append(path[:])
dfs(node.left, remaining - node.val, path)
dfs(node.right, remaining - node.val, path)
path.pop() # backtrack
dfs(root, target_sum, [])
return result