闯关leetcode——112. Path Sum

大纲

• 题目
• • 地址
  • 内容
• 解题
• • 代码地址

题目

地址

https://github.com/f304646673/leetcode/tree/main/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

解题

这题要检索一棵树从根节点到叶子节点的和，是否存在和给定值一致的情况。
这题的核心是对叶子节点的定义，即没有子节点。这样我们就可以在探索到没有左右子树的节点时，检测剩余未匹配的值是否为0来检测该路径是否符合要求。
只有左右子树中有任何一个路径匹配就直接返回，不用探索出所有可能方案。

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

        if (hasPathSum(root->left, targetSum)) return true;
        if (hasPathSum(root->right, targetSum)) return true;
        return false;
    }
};

代码地址

https://github.com/f304646673/leetcode/tree/main/112-Path-Sum