Space
Open
From Fieldwork
Scales
Archive
We have to take a leap of faith with induction. The dfs function promises that when it finishes executing, the prefix_sums map will be in the exact same state it was in before the function started.
We add one to the map, and we propagate it down to the branches. And we pop it off. And we trust that the children follow the instructions of the parent, because they hold the exact instruction sets.
We end up with a net 0 prefix_sums map at the end.
Other than the 0: 1 entry. That's the ground truth.
There's a lot of semantic meaning in the +1 and -1. These aren't merely isolated operations. These are the physical boundaries of the subproblem's scope.
Once we trust the induction, the code is trivial. We don't have to worry about "What if the left child changes the map?" because we know that the post-condition prevents that. We can focus entirely on the current node's responsibility:
Check the mile markers above you.
Leave your own mile marker for those above you.
Clean up before you leave.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
# map stores {prefix_sum : count}
# We initialize with {0: 1} to account for paths that
# equal targetSum starting exactly from the root.
prefix_sums = {0: 1}
def dfs(node, current_sum):
if not node:
return 0
# Update the running prefix sum
current_sum += node.val
# If (current_sum - targetSum) exists in our map,
# it means a valid path ends at this node.
num_paths = prefix_sums.get(current_sum - targetSum, 0)
# Add current_sum to the map for child nodes to use
prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
# Explore children
num_paths += dfs(node.left, current_sum)
# These don't share state because we backtrack.
num_paths += dfs(node.right, current_sum)
# Backtracking: remove the current sum from the map
# so it won't affect other branches
prefix_sums[current_sum] -= 1
return num_paths
return dfs(root, 0)
Practice 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