112. Path Sum

112. Path Sum

Summary

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Approach

DFS.

Calculate the sum from the root, and when we reach a leaf node, compare the sum with the target.

Function

Function dfs(root, total, target): If found[0]: return

If root is None: return

If root.left is None and root.right is None: # leaf found[0] = (total + root.val == target) return dfs(root.left, total + root.val, target) dfs(root.right, total + root.val, target)

Main: found = [False] dfs(root, 0, targetSum) return found[0]

Complexity

Time Complexity: O(N) Space Complexity: O(N)

Code refactored

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        
        if root.left is None and root.right is None:
            return root.val == targetSum
        
        remaining = targetSum - root.val
        return (
            self.hasPathSum(root.left, remaining) or
            self.hasPathSum(root.right, remaining)
        )

We can reduce targetSum for the next recursion.

This version avoids extra state such as found, so the code becomes simpler and cleaner.