题解 | #二叉树中是否存在节点和为指定值的路径#

建议大家在做回溯的时候，尽量把回溯写出来，比如当前层--，回溯上一层就++，而不要把回溯
的步骤隐藏起来。
小技巧：
搜索的时候有无返回值的做法：

//1、当搜索整棵树的时候，那么递归函数一般是不需要有返回值，但是也有例外，比如
<1>
    TreeNode* left = dfs(root->left);
    TreeNode* right = dfs(root->right);
    if(判断左右的逻辑)...
<2>
    if(...)...
    node->left = dfs(root->left);
    node->right = dfs(root->right);
    return node;
//2、当搜索其中一条符合条件的路径，递归函数就需要及时返回，下面常见的做法
<1>
    if(dfs(root->left)) //及时返回
        return ...
    if(dfs(root->right))
        return ...
    return ...

题目题解

    bool dfs(TreeNode *root, int sum) {
        if(!root) //空节点的出口
            return false;
        if(root && !root->left && !root->right && sum == 0) //叶子节点出口
            return true;
        if(root->left) {
            sum -= root->left->val;
            if(dfs(root->left, sum)) //如果为true 说明找到结果  及时退出
                return true;
            sum += root->left->val; //回溯
        }
        if(root->right) {
            sum -= root->right->val;
            if(dfs(root->right, sum))
                return true;
            sum += root->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)
            return false;
        return dfs(root, sum-root->val); //上面的搜索是从根节点的子树开始搜索 需要把根节点减去
    }