112. Path Sum

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

1. 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 are None), check if targetSum equals 0. - Recursively check the left and right subtrees.
2. Base Case: If the root node is None, return False.
3. Recursive Calls: - Update targetSum for the left child recursively. - Update targetSum for the right child recursively.
4. Return: Return True if a path sum equals the targetSum is found; otherwise, return False.

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);
};