# C# solution O(logN*logN) time O(1)space

• The basic idea is find the previous and next node of a specific node in in-order traversal. If we know the previous node and posterior node of a node, then we can judge this node is the wrong node or not.

``````public class Solution {
TreeNode big=null,small=null;
public void RecoverTree(TreeNode root) {
if(root==null)
return;
find(root,null,null);
int tmp=big.val;
big.val=small.val;
small.val=tmp;
return;
}
int find(TreeNode root,object pre,object post){

int front,back;
if(root.left==null){
if(pre==null)
front=root.val-1;
else
front=(int)pre;
}else{
front=find(root.left,pre,root.val);
}
if(root.right==null)
{
if(post==null)
back=root.val+1;
else
back=(int)post;
}else{
back=findleft(root.right);
}
if(front<root.val&&root.val>back&&big==null)
big=root;
if(front>root.val&&root.val<back)
small=root;
if(root.right!=null)
return find(root.right,root.val,post);
else
return root.val;

}
int findleft(TreeNode root){
if(root.left!=null)
return findleft(root.left);
return root.val;
}
``````

}

• It's not constant space because it's recursive and recursion uses stack space.

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