99. Recover Binary Search Tree Leetcode Java

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Solution:
In-order traversal.
The in-order traversal of a valid BST will be well-ordered. eg. 1,2,3,4,5,6
If two nodes are swapped by mistake, the traversal will become not sorted. And there are two possible swaps:
1. Two neighbors are swapped: eg. 1,2,4,3,5,6
2. Any other two elements are swapped: eg. 1,5,3,4,2,6
The difference between these two possible swaps are when we detect the unsorted arrays, the first case only have one dis-ordered sequence 4,3, while the second case has two, 5,3;  4,2.
So when we try to detect which two are swapped, we have to check how many unsorted sequence are there, if only 1 is detected, then the two elements in the sequence are swapped, if there are two unsorted sequence, first element in the first sequence and the second element in the second sequence are swapped.
I use Morris algorithm to conduct the in-order traversal in order to satisfy the constant space requirement.

  public void recoverTree(TreeNode root) {  
     if(root==null) return;  
     TreeNode node1=null;  
     TreeNode node2=null;  
     TreeNode pre=null;  
     TreeNode cur=root;  
     while(cur!=null){  
       if(cur.left==null){  
         if(pre!=null && cur.val<=pre.val) {  
             if(node1==null) node1=pre;  
             node2=cur;  
         }  
         pre=cur;  
         cur=cur.right;  
       }  
       else {  
         TreeNode preNode=cur.left;  
         while(preNode.right!=null && preNode.right!=cur) preNode=preNode.right;  
         if(preNode.right==null){  
           preNode.right=cur;  
           cur=cur.left;  
         }  
         else{  
           if(pre!=null && cur.val<=pre.val){  
             if(node1==null) node1=pre;  
             node2=cur;  
           }  
           preNode.right=null;  
           pre=cur;  
           cur=cur.right;  
         }  
       }  
     }  
     int temp=node1.val;  
     node1.val=node2.val;  
     node2.val=temp;  
   }