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