Path Sum
DFS subtracting each node's value; at a leaf, return whether the remainder is exactly zero.
2 min read
tree dfs
Problem#
Given the root of a binary tree and an integer targetSum, return whether some root-to-leaf path has values summing to targetSum.
Examples#
[5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22→true[1,2,3], targetSum = 5→false[], targetSum = 0→false
Constraints#
- The number of nodes is in
[0, 5000].
Approach#
Recursive DFS subtracting the current node’s value from the remaining target. At a leaf, success iff the remainder is zero.
Solution#
class Solution {public: bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; if (!root->left && !root->right) return targetSum == root->val; return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val); }};func hasPathSum(root *TreeNode, targetSum int) bool { if root == nil { return false } if root.Left == nil && root.Right == nil { return targetSum == root.Val } return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)}class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False if not root.left and not root.right: return targetSum == root.val return (self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val))function hasPathSum(root, targetSum) { if (root === null) return false; if (root.left === null && root.right === null) return targetSum === root.val; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null) return targetSum == root.val; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }}function hasPathSum(root: TreeNode | null, targetSum: number): boolean { if (root === null) return false; if (root.left === null && root.right === null) return targetSum === root.val; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}Editorial#
A leaf is a node with no children — that’s the only place we declare success or failure for a path. Internal nodes recurse into both children with the reduced target; || short-circuits on the first success.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#