112.路径总和

思路

递归需要把大问题化成小问题,我们从头开始看,

• 在根节点:求从根节点到叶子节点是否等于targetsum
• root->left:从此处到叶子节点的距离是否等于targetsum-root->val
• 以此类推到最后的叶子节点,判断最后的targetsum==root->val;

代码

bool hasPathSum(struct TreeNode* root, int targetSum) {
    if(root==NULL){
        return false;
    }
    if(root->left==NULL&&root->right==NULL){
        return targetSum==root->val;
    }
    return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}