牛客题霸 [二叉树中是否存在节点和为指定值的路径] C++题解/答案

题目描述

给定一个二叉树和一个值\ sum sum，判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径，
例如：
给出如下的二叉树，\ sum=22 sum=22，

返回true，因为存在一条路径 5\to 4\to 11\to 25→4→11→2的节点值之和为 22

题解：

不断递归左右子树，递归过程中不断用sum-当前节点的值，到叶子节点的是否特判sum减去叶子节点是否为0
注意，要先判断root是否为NULL，再判断左右子树的情况，否则会段错误

代码：

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */

class Solution {
   
public:
    /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */
    bool hasPathSum(TreeNode* root, int sum) {
   
        // write code here
        if(root==NULL)return 0;
        if(root->left==NULL&&root->right==NULL&&sum-(root->val)==0)return 1;
        
        return hasPathSum(root->left,sum-(root->val))||hasPathSum(root->right,sum-(root->val));
    }
};