The same algorithm and inputs but the results are different between submission and test case


  • 0
    L

    Hi, I want to solve this problem by using a simple stack and a non-recursive algorithm
    But I encountered a strange error looks like below

    Submission Result: Wrong Answer More Details 
    51 / 54 test cases passed.
    Input:
    [1,null,2,4,null,null,3], [1,null,2,4,null,null,3]
    Output:
    false
    Expected:
    true
    

    I input this two trees in the custom test case and run the same code
    the result is as below

    Run Code Result:
    
    Your input
    
    [1,null,2,4,null,null,3]
    [1,null,2,4,null,null,3]
    Your answer
    
    true
    Expected answer
    
    true
    Runtime: 0 ms
    

    The code are the same in submission and custom test case but the results are different.
    I don't know how to debug this error. Hopefully someone will help me.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    #define STACK_SIZE 10000
    int stack_top = 0;
    struct SavedNode 
    {
        struct TreeNode* p;
        struct TreeNode* q;
    };
    
    struct SavedNode stack[STACK_SIZE];
    void push( struct TreeNode* p, struct TreeNode* q )
    {
        if( p ==  NULL || q == NULL)
        {
        return;    
        }
        if( stack_top < STACK_SIZE)
        {
        stack[stack_top].p = p;
        stack[stack_top].q = q;
        stack_top++;      
        }
        else
        {
            return;
        }
    
    }
    
    struct SavedNode* pop()
    {
        if( stack_top <= 0 )
        {
            return NULL;
        }
        stack_top--;
        return &(stack[stack_top]);
    }
    bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
    {
        bool p_hasLeft = false;
        bool p_hasRight = false;
        bool q_hasLeft = false;
        bool q_hasRight = false;
        struct TreeNode* ptr_p = p;
        struct TreeNode* ptr_p_left = NULL;
        struct TreeNode* ptr_q = q;
        struct TreeNode* ptr_q_left = NULL;
        
        if( p != NULL && q == NULL )
        {
            return false;
        }
        else if( p == NULL && q != NULL )
        {
            return false;
        }
        else if( p == NULL && q == NULL )
        {
            return true;
        }
        
        ptr_p_left = p->left;
        ptr_q_left = q->left;
    
        while( ptr_p != NULL )
        {
        p_hasLeft = ptr_p->left != NULL ? true : false;
        p_hasRight = ptr_p->right != NULL ? true : false;    
        q_hasLeft = ptr_q->left != NULL ? true : false;
        q_hasRight = ptr_q->right != NULL ? true : false;
    
        if( ( ptr_p->val != ptr_q->val ) ||
          p_hasLeft != q_hasLeft ||
          p_hasRight != q_hasRight )
          {
              return false;
          }
          if( ptr_p_left != NULL && ptr_p->right != NULL )
          {
              push( ptr_p, ptr_q );
              ptr_p = ptr_p->left;
              ptr_q = ptr_q->left;
              ptr_p_left = ptr_p->left;
              ptr_q_left = ptr_q->left;
          }
          else if( ptr_p_left != NULL && ptr_p->right == NULL )
          {
              ptr_p = ptr_p->left;
              ptr_q = ptr_q->left;
              ptr_p_left = ptr_p->left;
              ptr_q_left = ptr_q->left;
          }
          else if( ptr_p_left == NULL && ptr_p->right != NULL )
          {
              ptr_p = ptr_p->right;
              ptr_q = ptr_q->right;
              ptr_p_left = ptr_p->left;
              ptr_q_left = ptr_q->left;
          }
          else
          {
              struct SavedNode *temp = pop();
              if( temp != NULL )
              {
              ptr_p = temp->p;
              ptr_q = temp->q;
              ptr_p_left = NULL;
              ptr_q_left = NULL;    
              }
              else
              {
                  return true;
              }
          }
        }
        return true;
    }

Log in to reply
 

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