Can't figure out why I keep getting this run time error! Help!


  • 0
    V
    class Solution {
    public:
        bool hasPath(TreeNode *node, int rest){
            if (node == NULL)// node doesn't exist or this path is wrong
            {
                return false;
            }
            else if(node -> left == NULL && node -> right == NULL ) //reached leaf 
            {
                if  (rest == 0)  //path sum up correctly
                    return true;
                else 
                    return false;
            }
           else if ( rest <= 0) //hasn't reached leaf but sum decreased to 0 or below already
           {
                return false;
            }
            else
            {
                return hasPath(node->left,rest - node->left->val) || hasPath(node->right,rest - node->right->val);
            }
            
        }
    bool hasPathSum(TreeNode *root, int sum) {
        if(root == NULL)
        {
            return false;
        }
        else
        {
            bool flag = hasPath(root, sum - root->val);
            return flag;
        }
    }
    

    };


  • 0
    S

    First of all, it's not guaranteed that the value of node is positive, this won't cause runtime error though:

    else if ( rest <= 0) //hasn't reached leaf but sum decreased to 0 or below already
    {
        return false;
    }
    

    Second, the following line from your code would cause cause runtime error since node->left or node->right would be NULL:

    return hasPath(node->left,rest - node->left->val) || hasPath(node->right,rest - node->right->val);
    

    Your solution is almost right but you should organize your logic more carefully:

    bool hasPathSum(TreeNode *root, int sum)
    {
        if ( root == NULL )
        {
            return false;
        }
        sum -= root->val;
        return ( root->left == NULL && root->right == NULL && sum == 0 )
            || ( root->left != NULL && this->hasPathSum(root->left, sum) )
            || ( root->right != NULL && this->hasPathSum(root->right, sum) );
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.