TLE for a Morris Traversal solution?


  • 1
    X

    My O(n) solution worked. However, in order to use O(1) space, I had to use the Morris traversal solution. But OJ gave TLE. Someone could help out as to why?

    def recoverTree(self,root):#Morris Traversal to save space
                current=root;pred=None;pred1=cur1=pred2=cur2=None;
                while(current!=None):
                        if(current.left==None):pred=current;current=current.right
                        else:
                                pre=current.left
                                while(pre.right!=None and pre.right!=current):pre=pre.right
                                if(pre.right==None):#first time, vary node
                                        pre.right=current;current=current.left
                                else:#second time, print and undo the "vary"
                                        pred=current;pre.right=None;current=current.right
                        if(pred!=None and current!=None and pred.val >=current.val):
                                if(pred1==None):pred1=pred;cur1=current
                                else:pred2=pred;cur2=current
                if(pred1!=None and cur2!=None):#4231 and #3214 case
                        tmp=pred1.val;pred1.val=cur2.val;cur2.val=tmp
                else:
                        tmp=pred1.val;pred1.val=cur1.val;cur1.val=tmp
                return root

  • 2
    X

    I just realized how stupid I was. Here is the correct python solution:

    def recoverTree(self, root):
            runner=root;previous=None;node1=None;node2=None
            while(runner):
                if(runner.left==None):
                    if(previous!=None and previous.val>runner.val):
                        if(node1==None):node1=previous;node2=runner
                        else:node2=runner
                    previous=runner;runner=runner.right
                else:
                    pre=runner.left
                    while(pre.right!=None and pre.right!=runner):pre=pre.right
                    if(pre.right==None):pre.right=runner;runner=runner.left
                    else:
                        if(previous!=None and previous.val>runner.val):
                            if(node1==None):node1=previous;node2=runner
                            else:node2=runner
                        pre.right=None;previous=runner;runner=runner.right
            tmp=node1.val
            node1.val=node2.val
            node2.val=tmp
            return root

  • 0
    S

    I don't even know you can write Python like that; use blank spaces please... >_<


Log in to reply
 

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