Practice/Meta/Leetcode 112. Path Sum

Leetcode 112. Path Sum

CodingMust

Problem

Given a binary tree and an integer target sum, determine if there exists a path from the root to any leaf node where the sum of all node values along that path equals the target sum.

A leaf node is defined as a node that has no children (both left and right pointers are null).

Requirements

1. Check all possible root-to-leaf paths in the tree
2. Return true if any path's sum equals the target, false otherwise
3. A path must end at a leaf node (not just any node)
4. Handle the case where the tree is empty

Constraints

• The number of nodes in the tree is in the range [0, 5000]
• -1000 ≤ Node.val ≤ 1000
• -1000 ≤ targetSum ≤ 1000
• Expected time complexity: O(n) where n is the number of nodes
• Expected space complexity: O(h) where h is the height of the tree (recursion stack)

Examples

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The path 5→4→11→2 has a sum of 5+4+11+2 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5 Output: false Explanation: The two paths are 1→2 (sum=3) and 1→3 (sum=4), neither equals 5

Example 3:

Input: root = [], targetSum = 0 Output: false Explanation: An empty tree contains no paths

Example 4:

Input: root = [1,2], targetSum = 1 Output: false Explanation: Even though the root equals 1, it's not a leaf node. The only path is 1→2 (sum=3)