112.path sum leetcode wong answer for two test cases

Question

problem My code fails for the following test case. I don't understand why. Can you tell me where I went wrong? My code passes (114/116) test cases. I'm doing DFS and checking whether currSum==targetSum and if it satisfies this condition and it's also a leaf node I'm setting global variable ```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;        
    }
};

https://stackoverflow.com/a/68159325/1625187 – Evg Aug 05 '21 at 05:39 — Evg, Aug 05 '21 at 05:39

score 1 · Answer 1 · answered Aug 05 '21 at 06:57

Here is a simple intuitive solution for 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);
    }
};

score 0 · Accepted Answer · answered Aug 05 '21 at 05:38

The code works fine and the logic is perfect, you forgot to put brackets to the if statement

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

Here's the full code

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;        
    }
};

score 0 · Answer 3 · answered Aug 05 '21 at 05:39

0

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

This is wrong. You will return even if the condition doesn't satisfy. As there are negative values, it might be possible that the sum becomes targetSum again at a leaf node after further operations.

Correct:

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

answered Aug 05 '21 at 05:39

Staz

348
1
2
6

Thanks, I really appreciate your help – anfjnlnl Aug 05 '21 at 05:46

112.path sum leetcode wong answer for two test cases

3 Answers3