TLE for a Morris Traversal solution?

• 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``````

• 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``````

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

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