Path Sum

112. 路径总和

分析

从根节点开始，每次将当前节点值 root->val 从 targetSum 中减去
如果当前节点是叶子节点，判断此时 targetSum == root->val 是否成立
否则递归判断左子树和右子树中是否有满足条件的路径

时间复杂度

时间复杂度 O(n)，最坏情况下每个节点都要访问一次

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    bool hasPathSum(TreeNode* root, int targetSum)
    {
        if (!root) return false;  // 空节点，返回 false

        // 到达叶子节点，检查当前值是否等于剩余的目标和
        if (!root->left && !root->right)
            return targetSum == root->val;

        // 递归左子树
        if (root->left && hasPathSum(root->left, targetSum - root->val))
            return true;

        // 递归右子树
        if (root->right && hasPathSum(root->right, targetSum - root->val))
            return true;

        // 左右子树都不满足条件
        return false;
    }
};