Runtime error but running fine locally


  • 0
    S

    Hi,

    I'm hitting runtime error but can't figure out why.
    the implementation is running fine locally and I closely read the code line by line and did find anything wrong. wondering if anyone here can give a hint.

    the case triggering runtime error is very simple: (2, #, 1)

    struct incorrectLog{
        int depth;
        int numOfError; // 1 means only 1 substree has incorrect data, 2 means both left and right have incorrect data
        TreeNode* ToBeSwapped1;
        TreeNode* ToBeSwapped2;
    
        incorrectLog() : depth(INT_MAX), numOfError(0), ToBeSwapped1(NULL), ToBeSwapped2(NULL){}
    };
    
    incorrectLog topError;
    
    Boundary findBondariesAndErrors(TreeNode* root, const int depth){
        Boundary output;
        if (root == NULL){
            return output;
        }
        if ((root->left == NULL) && (root->right == NULL)){
            output.Max = root->val;
            output.Min = root->val;
            output.pMax = output.pMin = root;
            return output;
        }
    
        Boundary leftSubtreeBoundaries;
        Boundary rightSubtreeBoundaries;
    
        if (root->left){
            leftSubtreeBoundaries = findBondariesAndErrors(root->left, depth + 1);
        }
    
        if (root->right){
            rightSubtreeBoundaries = findBondariesAndErrors(root->right, depth + 1);
        }
    
        if ((leftSubtreeBoundaries.Max > root->val) && (rightSubtreeBoundaries.Min < root->val)){
            // sibling swap
            if (topError.depth > depth){
                topError.depth = depth;
                topError.numOfError = 2;
                topError.ToBeSwapped1 = leftSubtreeBoundaries.pMax;
                topError.ToBeSwapped2 = rightSubtreeBoundaries.pMin;
            }
        }
        else if (leftSubtreeBoundaries.Max > root->val){
            // left subtree incorrect
            if (topError.depth > depth){
                topError.depth = depth;
                topError.numOfError = 1;
                topError.ToBeSwapped1 = leftSubtreeBoundaries.pMax;
                topError.ToBeSwapped2 = root;
            }
        }
        else if (rightSubtreeBoundaries.Min < root->val){
            // right subtree incorrect
            if (topError.depth > depth){
                topError.depth = depth;
                topError.numOfError = 1;
                topError.ToBeSwapped1 = rightSubtreeBoundaries.pMin;
                topError.ToBeSwapped2 = root;
            }
        }
    
        // record the max
        if (leftSubtreeBoundaries.Max > rightSubtreeBoundaries.Max){
            if (root->val > leftSubtreeBoundaries.Max){
                output.Max = root->val;
                output.pMax = root;
            }
            else{
                output.Max = leftSubtreeBoundaries.Max;
                output.pMax = leftSubtreeBoundaries.pMax;
            }
        }
        else{
            if (root->val > rightSubtreeBoundaries.Max){
                output.Max = root->val;
                output.pMax = root;
            }
            else{
                output.Max = rightSubtreeBoundaries.Max;
                output.pMax = rightSubtreeBoundaries.pMax;
            }
        }
    
        // record the min
        if (leftSubtreeBoundaries.Min < rightSubtreeBoundaries.Min){
            if (root->val < leftSubtreeBoundaries.Min){
                output.Min = root->val;
                output.pMin = root;
            }
            else{
                output.Min = leftSubtreeBoundaries.Min;
                output.pMin = leftSubtreeBoundaries.pMin;
            }
        }
        else{
            if (root->val < rightSubtreeBoundaries.Min){
                output.Min = root->val;
                output.pMin = root;
            }
            else{
                output.Min = rightSubtreeBoundaries.Min;
                output.pMin = rightSubtreeBoundaries.pMin;
            }
        }
    
        return output;
    }
    
    class Solution {
    public:
        void recoverTree(TreeNode *root) {
            // filter out basic cases
            if (root == NULL){
                // zero node
                return;
            }
            if ((root->left == NULL) && (root->right == NULL)){
                // single node
                return;
            }
    
            findBondariesAndErrors(root, 0);
            if (topError.depth != INT_MAX){
                swap(topError.ToBeSwapped1->val, topError.ToBeSwapped2->val);
            }
    
        }
    };

  • 0
    S

    I found the issue, but doesn't really know why.

    it turns out I need to re-initialize the errorLog struct. the struct initialization should be done by the default constructor that I put in the struct definition. it behaves so on my VS 2013 environment too.
    after adding the 4 lines:
    topError.depth = INT_MAX;
    topError.numOfError = 0;
    topError.ToBeSwapped1 = NULL;
    topError.ToBeSwapped2 = NULL;
    the implementation got accepted.

    class Solution {
    public:
        void recoverTree(TreeNode *root) {
            // filter out basic cases
            if (root == NULL){
                // zero node
                return;
            }
            if ((root->left == NULL) && (root->right == NULL)){
                // single node
                return;
            }
    
            topError.depth = INT_MAX;
            topError.numOfError = 0;
            topError.ToBeSwapped1 = NULL;
            topError.ToBeSwapped2 = NULL;
            findBondariesAndErrors(root, 0);
            if (topError.depth != INT_MAX){
                swap(topError.ToBeSwapped1->val, topError.ToBeSwapped2->val);
            }
    
        }
    };

  • 0
    S

    does this mean OJ compiler isn't doing right? or VS compiler is doing too much beyond the spec?


Log in to reply
 

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