112.path sum leetcode wong 两个测试用例的答案

Question

problem 我的代码在以下测试用例中失败。我不明白为什么。你能告诉我哪里出错了吗？我的代码通过了 (114/116) 个测试用例。我正在做 DFS 并检查是否 currSum==targetSum 并且它是否满足此条件并且它也是一个叶节点我正在设置全局变量```flag = true``。

[1,-2,-3,1,3,-2,null,-1]
-1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flag=false;
    void dfs(TreeNode *root, int currSum, int targetSum){
        if(root==NULL) return ;
        // cout<<currSum<<" ";
        currSum+=root->val;
        cout<<currSum<<" ";
        if(currSum == targetSum) {
            if(root->left==NULL && root->right==NULL) flag=true;
            return;
        }
        
        // else if(abs(currSum)>abs(targetSum)) return;
        dfs(root->left,currSum,targetSum);
        dfs(root->right,currSum,targetSum);
    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
        int currSum=0;
        dfs(root,currSum,targetSum);
        return flag;        
    }
};

Answer 1

代码运行良好，逻辑完美，你忘了给 if 语句加上括号

        if(root->left == NULL && root->right == NULL) {
            flag=true;
            return;
        }

这是完整的代码

class Solution {
public:
    bool flag = false;
    void dfs(TreeNode *root, int currSum, int targetSum){
        if(root == NULL) return ;
        currSum += root->val;
        if(currSum == targetSum) {
            if(root->left==NULL && root->right==NULL) {
                flag=true;
                return;
            }
        }
        dfs(root->left,currSum,targetSum);
        dfs(root->right,currSum,targetSum);
    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
        int currSum=0;
        dfs(root,currSum,targetSum);
        return flag;        
    }
};

Answer 2

if(root->left==NULL && root->right==NULL) flag=true;
return;

这是错误的。即使条件不满足，你也会return。由于存在负值，因此在进一步操作后，sum可能会在叶节点处再次变为targetSum。

正确：

if(root->left==NULL && root->right==NULL){
    flag = true;
    return;
}

Answer 3

这是Path Sum Leetcode

的一个简单直观的解决方案

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->right && !root->left) return root->val==sum;
        return hasPathSum(root->left, sum-root->val) ||
               hasPathSum(root->right, sum-root->val);
    }
};

112.path sum leetcode wong 两个测试用例的答案

112.path sum leetcode wong answer for two test cases

c++

depth-first-search