Introduction

In this blog post, we will explore how to solve the LeetCode problem "112" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000

Explanation

Here's a solution that efficiently determines if a binary tree has a root-to-leaf path that sums to a given target sum.

• Recursive Depth-First Search: Traverse the tree using a recursive DFS approach. At each node, subtract the node's value from the target sum.
• Leaf Node Check: If we reach a leaf node (no left and right children), check if the remaining target sum is zero. If it is, we've found a path with the desired sum.

• Early Termination: If the current node is null, it means there is no path so return false.

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once. Space Complexity: O(H), where H is the height of the tree. In the worst case (skewed tree), H = N, resulting in O(N) space. In the best case (balanced tree), H = log N, resulting in O(log N) space.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def hasPathSum(root: TreeNode, targetSum: int) -> bool:
    if not root:
        return False

    def hasPathSumHelper(node: TreeNode, currentSum: int) -> bool:
        if not node:
            return False

        currentSum -= node.val

        if not node.left and not node.right:
            return currentSum == 0

        return hasPathSumHelper(node.left, currentSum) or hasPathSumHelper(node.right, currentSum)

    return hasPathSumHelper(root, targetSum)