SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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