Problem
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that the sum of all node values along the path equals targetSum. Otherwise, return false.A leaf node is a node with no left or right child.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Output
true Solution
This solution uses Depth-First Search (DFS) with recursion. As we move from the root toward a leaf, the current node's value is subtracted from targetSum.When a leaf node is reached, we check whether its value is equal to the remaining target. If it is, a valid root-to-leaf path exists.
The recursion continues through both subtrees until a valid path is found or all possible paths have been checked.
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// 1. Base case: If the node is null, no path exists.
if (root == null) {
return false;
}
// 2. Leaf check: Verify whether the remaining sum matches the leaf's value.
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
// 3. Recursive step: Subtract the current node value and check both subtrees.
int remainingSum = targetSum - root.val;
return hasPathSum(root.left, remainingSum)
|| hasPathSum(root.right, remainingSum);
}
}
Complexity
In the worst case, every node in the binary tree may be visited, resulting in a time complexity ofO(n). The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.