LeetCode //C - 112. Path Sum

112. Path Sum

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 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

From: LeetCode
Link: 112. Path Sum

---

Solution:

Ideas：

1. Base Cases:

• If the current node (root in the code) is NULL, we return false because a null node cannot be part of any path.
• If the current node is a leaf node (i.e., it has no left or right child), we check if its value is equal to the remaining targetSum. If it is, then this node completes a path from the root to a leaf that sums up to the original target, and we return true.

2. Recursive Step:

• From the remaining targetSum, subtract the value of the current node. This is because as we traverse down the tree, we need to account for the values of the nodes we’ve visited.
• Then, we recursively check both the left and right subtrees using the adjusted targetSum.
  • If either of the recursive calls returns true, it means there’s a path in that subtree that sums up to the target. Hence, we return true.

3. How It Works:

• Imagine we start at the root of the tree with a certain targetSum.
• As we move down the tree, we keep reducing the targetSum by the value of the current node.
• If we reach a leaf node and the targetSum matches the value of that leaf node, then we’ve found a path from the root to this leaf that sums to the original target.
• If not, we backtrack and try other paths.

Essentially, this recursive approach explores all possible root-to-leaf paths in the tree, checking if any of them sum up to the given target. The beauty of this approach is its simplicity: by adjusting the target as we traverse, we avoid having to explicitly track the path or its sum.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool hasPathSum(struct TreeNode* root, int targetSum) {
    // Base cases
    if (!root) return false;
    if (!root->left && !root->right) return root->val == targetSum;

    // Subtract the value of the current node from targetSum
    targetSum -= root->val;

    // Recursively check the left and right subtrees
    return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19