🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve this problem, we need to traverse the tree from the root to each leaf node, keeping track of the current path sum. Whenever we reach a leaf node, we check if the current path sum equals the target sum.
Approach
- Recursive Depth-First Search (DFS): Implement a recursive function that traverses the tree.
- Subtract the node's value from the
targetSum
at each node. - If we reach a leaf node (both children areNone
), check iftargetSum
equals 0. - Recursively check the left and right subtrees. - Base Case: If the root node is
None
, returnFalse
. - Recursive Calls:
- Update
targetSum
for the left child recursively. - UpdatetargetSum
for the right child recursively. - Return: Return
True
if a path sum equals thetargetSum
is found; otherwise, returnFalse
.
Complexity
Time Complexity:
( O(n) ), where ( n ) is the number of nodes in the binary tree. Each node is visited once.
Space Complexity:
( O(h) ), where ( h ) is the height of the tree, representing the recursion stack space in the worst case scenario of a skewed tree.
Code
C++
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum)
{
if (root == nullptr) {
return false;
}
targetSum -= root->val;
if (root->left == nullptr && root->right == nullptr) {
return targetSum == 0;
}
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
};
Python
class Solution:
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
if not root:
return False
targetSum -= root.val
if not root.left and not root.right:
return targetSum == 0
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
Java
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
targetSum -= root.val;
if (root.left == null && root.right == null) {
return targetSum == 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}
JavaScript
var hasPathSum = function(root, targetSum)
{
if (root == null) {
return false;
}
targetSum -= root.val;
if (root.left == null && root.right == null)
{
return targetSum == 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};