Space
Open
From Fieldwork
Scales
Archive
This is actually quite elegant as a thing to study.
Tree problems are about asking: "What is the one question I need to answer at each node, and how do I transform the input so that question is trivial to ask?"
The kernel of recursion is delegation and local perspective. We reduce complexity as much as possible along each step of the way.
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
# If it's a leaf, it has to be the value
if not root.left and not root.right:
return root.val == targetSum
remaining = targetSum - root.val
return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)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