# Got TLE for {2,3,1}, but it takes 0ms in eclipse

• Hi all, I'm getting problem with the code below, please take a look at it if you've got time.
I used Morris inorder traversal to find the wrong nodes and switch them, but got stuck at the test case{2,3,1}. I tested it on my eclipse, and it cost 0ms for this case, so what's wrong here?
Thank you!

``````public class Solution {
public void recoverTree(TreeNode root) {
TreeNode cur = root;
TreeNode mis1 = null;
TreeNode mis2 = null;
TreeNode prev = null;
TreeNode tmp=root;

while(cur!=null){
if(cur.left==null){
if(prev!=null){
if(prev.val>cur.val){
if(mis1==null) {mis1=prev;mis2=cur;}
else {mis2=cur;break;}
}
}
prev=cur;
cur=cur.right;
}
else{
tmp=cur.left;
while(tmp.right!=null&&tmp.right!=cur) tmp=tmp.right;
if(tmp.right==null){
tmp.right=cur;
cur=cur.left;
}
else{
if(prev!=null){
if(prev.val>cur.val){
if(mis1==null) {mis1=prev;mis2=cur;}
else {mis2=cur;break;}
}
}
tmp.right=null;
prev=cur;
cur=cur.right;
}
}
}
int tmpval = mis2.val;
mis2.val=mis1.val;
mis1.val=tmpval;
}
``````

}

• Morris inorder traversal modifies the original BST structure.
It's your duty to restore the structure.

TLE comes from OJ checking.

Just remove all "BREAK"; let the while loop finish the job before swapping values.

You only need find the two element. and swap the value.

`````` TreeNode *last =NULL, *first = NULL, *second = NULL;

void reco(TreeNode *node) {
if (!node) return ;

reco(node->left);

if (last) {
if (!first) {
if (last->val > node->val) {
first = last;
second = node;
}
}else {
if (last->val > node->val) {
second = node;
}
}

}

last = node;
reco(node->right);
}

void recoverTree(TreeNode *root) {
if (!root) return;

reco(root);

if (first && second) {
first->val = first->val ^ second->val;
second->val = first->val ^ second->val;
first->val = first->val ^ second->val;
}

}``````

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