💬 Discord
Sign In
NeetCode #394LC-112EasyTrees
← Back to All Problems

#394 · #112 · Path Sum(路径总和)

📌 Problem Statement & Constraints

Given the root of a binary tree and an integer targetSum, return true if there is a root-to-leaf path whose values sum to the target. Constraints: the number of nodes is in [0, 5000], -1000 <= Node.val, targetSum <= 1000.

💡 Core Algorithmic Approaches

  1. Subtract the current value from the target as you descend.
  2. At a leaf, the path sum equals the target exactly when the remaining value is 0.
  3. The leaf test must be not node.left and not node.right -- a node with one child is not a leaf, so its missing branch must not be treated as a path end.
  4. Return True as soon as either branch succeeds.

💻 Benchmark Python3 Implementation

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        remaining = targetSum - root.val
        if not root.left and not root.right:
            return remaining == 0          # leaf -> path complete
        return (self.hasPathSum(root.left, remaining)
                or self.hasPathSum(root.right, remaining))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited at most once (with early exit).
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Checking remaining == 0 at any node rather than only at a leaf: a partial path could sum to the target and produce a false positive.
  • Treating a node with one child as a leaf: the path must end at a true leaf.
  • Using root.val == targetSum at the root only: the path must be root-to-leaf, so the recursion must continue.
  • Assuming values are positive: they can be negative, so pruning on the remaining sum is invalid.