Given the root of a binary tree and an integer targetSum, return true if some path from the root down to a leaf has node values adding up to targetSum. A leaf is a node with no children.
Example 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
The path 5, 4, 11, 2 sums to 22.
Example 2
Input: root = [1,2,3], targetSum = 5
Output: false
Constraints
- The number of nodes is in the range 0 to 5000
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Hints
Frequently asked at: Amazon, Microsoft, Meta
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
You could collect every root to leaf path and add up each one, but that copies paths and wastes memory. Instead carry the remaining target down the tree: at a node with value v, the rest of the path must add up to target - v. When we reach a leaf, the path works exactly when the remaining target equals the leaf value. Each node is visited once.
Algorithm
- If
rootis null, returnfalse. - If
rootis a leaf, returnroot.val == targetSum. - Otherwise recurse on both children with
targetSum - root.valand returntrueif either succeeds.
Time:
O(n)Space: O(h) recursion depthInterview tip: An empty tree with
targetSum = 0 must return false, and the check must happen only at leaves: in [1,2] with target 1, node 1 alone is not a valid path because it has a child.class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False if not root.left and not root.right: # leaf return root.val == targetSum remain = targetSum - root.val return self.hasPathSum(root.left, remain) or self.hasPathSum(root.right, remain)Ctrl + Enter runs the examples