To solve this problem, we need to determine if there exists a root-to-leaf path in a binary tree such that the sum of the values along this path equals a given target sum. A leaf node is defined as a node with no left or right children.

Approach

The problem can be efficiently solved using a recursive approach, leveraging the natural structure of binary trees. Here's the step-by-step breakdown:

1. Base Case: If the root is null, there are no paths, so return false.
2. Leaf Node Check: If the current node is a leaf (both left and right children are null), check if its value equals the remaining target sum (since we subtract the current node's value from the target sum as we traverse down the tree).
3. Recursive Traversal: For non-leaf nodes, recursively check if either the left or right subtree contains a path that sums up to the remaining target sum (target sum minus the current node's value).

Solution Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

        # Check if current node is a leaf
        if not root.left and not root.right:
            return root.val == targetSum

        # Recurse on left and right subtrees with updated target sum
        remaining_sum = targetSum - root.val
        return self.hasPathSum(root.left, remaining_sum) or self.hasPathSum(root.right, remaining_sum)

Explanation

• Base Case Handling: When the root is null, there are no paths, so we return false.
• Leaf Node Check: For a leaf node, we directly compare its value with the target sum (since it's the end of the path).
• Recursive Traversal: For non-leaf nodes, we reduce the target sum by the current node's value and check if either subtree can reach the reduced target sum. This works because the path from the root to any leaf must pass through the current node, so the remaining sum needed is the target sum minus the current node's value.

Key Notes

• Efficiency: The recursive approach runs in O(n) time complexity, where n is the number of nodes in the tree, since each node is visited exactly once.
• Space Complexity: The space complexity is O(h) (h being the height of the tree) due to the recursion stack. For a balanced tree, h is O(log n), and for an unbalanced tree, h can be O(n) (worst case).

This approach is concise, easy to understand, and handles all edge cases (like negative values, single-node trees, and empty trees) correctly.

Alternative Iterative Approach: For those who prefer an iterative solution (to avoid recursion stack overflow for very deep trees), here's an implementation using a stack:

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

        stack = [(root, root.val)]

        while stack:
            node, current_sum = stack.pop()

            # Check if current node is a leaf
            if not node.left and not node.right:
                if current_sum == targetSum:
                    return True

            # Push right child first so left is processed first (order doesn't affect correctness)
            if node.right:
                stack.append((node.right, current_sum + node.right.val))
            if node.left:
                stack.append((node.left, current_sum + node.left.val))

        return False

This iterative approach uses a stack to keep track of nodes and their cumulative sum from the root. It processes each node and checks if it's a leaf with the desired sum, returning true if found, else false after all nodes are processed. The time and space complexity are the same as the recursive approach.

Both approaches are valid, but the recursive one is more straightforward for this problem. Choose the one that best fits your needs! ✨

作者声明:本文包含人工智能生成内容。