Space
Open
From Fieldwork
Scales
Archive
Depth First Search (DFS) with Backtracking.
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
result = []
def dfs(node, remaining_sum, current_path):
if not node:
return
# 1. Add current node to path and update sum
current_path.append(node.val)
# 2. Check if it's a leaf node and sum matches
if not node.left and not node.right and remaining_sum == node.val:
# Important: Append a copy ([:]) of the list,
# otherwise backtracks will affect the result.
result.append(current_path[:])
# 3. Traverse children
else:
dfs(node.left, remaining_sum - node.val, current_path)
dfs(node.right, remaining_sum - node.val, current_path)
# 4. Backtrack: Remove current node to prepare for the next branch
current_path.pop()
dfs(root, targetSum, [])
return resultPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode