牛客BM29-二叉树中和为某一值的路径（-）-C++

一、运行结果

二、题目

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

三、思路

这里通过深度优先遍历的方式实现，找到从根结点到所有叶子结点的路径，只要其中有一条路径的长度等于给定的长度，就表示存在满足题意的路径，若所有的路径长度和给定长度都不相同，则表示不存在。

四、代码

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        int cursum = 0; //当前路径的长度
        return dfs(root, sum, cursum);
    }
    bool dfs(TreeNode * root, int sum, int cursum){
        if(root == NULL) return false;
        cursum += root->val;
        if(root->left == NULL && root->right == NULL){ //叶子节点
            if(cursum == sum) return true;
        }  //看左右子树是否有满足题意的路径
        return dfs(root->left, sum, cursum) || dfs(root->right, sum, cursum);
    }
};