Weird Time Limit Exceeded Error (Using Morris Traversal in c++)


  • 0
    U

    My program ends in the OJ but it still reports Time Limit Exceeded. I have explicitly printed program end using cout.

    I don't expect anyone to understand my code but see why I am getting Time Limit Exceeded when program is ending.

    Here is my code:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    TreeNode* firstNode,*secondNode;
    int flag;
    void checkNode(TreeNode* &node1, TreeNode* &node2 ){
        if(node2==NULL)
            return;
        if(node1->val>node2->val && flag==0){
          //  cout<<"firstnode"<<endl;
            firstNode = node1;
            secondNode = node2;
            flag=1;
         //   if(firstNode==NULL)
        //        cout<<"FirstNode is null in the function"<<endl;
        }
        else if(node1->val>node2->val && flag==1){
            int temp = node2->val;
            node2->val = firstNode->val;
            firstNode->val = temp;
            flag=2;
           // cout<<"Nodes Swapped"<<endl;
        }
    } 
     
    class Solution {
    public:
        
        
        void recoverTree(TreeNode* root) {
            flag=0;
            TreeNode* current=root,*node1=NULL,*node2=NULL,*temp;
            while(current){
             //   cout<<"current:"<<current->val<<endl;
                if(current->left){
                    temp = current->left;
                    while(temp->right!=NULL && temp->right!=current){
                        temp=temp->right;
                    }
                    if(temp->right==NULL){
                        temp->right=current;
                        current=current->left;
                    }
                    else{
                        temp->right=NULL;
                        if(node1==NULL)
                            node1=current;
                        else if(node2==NULL)
                            node2=current;
                        else{
                            node1=node2;
                            node2=current;
                        }
           //             cout<<"Before checking 1:"<<endl;
                        checkNode(node1,node2);
          //              cout<<"flag:"<<flag<<endl;
                        if(flag==2){
                            
                            current=NULL;
                        
                            
                        }
                        else 
                        current=current->right;
                    //    if(current==NULL)
                     //       cout<<"yes"<<endl;
                     //   if(firstNode==NULL)
          //                  cout<<"FirstNode is null after returning"<<endl;
                    }
                        
                }
                else {
                    if(node1==NULL)
                        node1=current;
                    else if(node2==NULL)
                        node2=current;
                    else{
                        node1=node2;
                        node2=current;
                    }
                    
           //         cout<<"Before checking 2:"<<endl;
                    checkNode(node1,node2);
          //          cout<<"blahflag:"<<flag<<endl;
                    if(flag==2)
                        current=NULL;
                    else
                    current=current->right;
                }
            }
         //   cout<<"Swapping end"<<endl;
            if(flag==1){
                
             //   if(firstNode==NULL)
             //       cout<<"firstNode is Null";
                    
              //  if(secondNode==NULL)
              //      cout<<"SecondNode is Null";
                    
                int temp = firstNode->val;
                firstNode->val = secondNode->val;
                secondNode->val = temp;
            }
            cout<<"Program Ends"<<endl;
        }
    };

  • 0
    T

    Morris modifies the tree structure, maybe you didn't manage to restore the structure properly and introduced a circle, which, when checking the result or printing the expected/actualy ends up in an infinite loop.

    I can prove this by the following extremely simple malicious code run on any input:

    void recoverTree(TreeNode* root) {
        if (root) {
            root->left = root;
            root->right = root;
        }
    }

Log in to reply
 

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