LeetCode OJ - Recover Binary Search Tree

 1 /**
 2      * Two elements of a binary search tree (BST) are swapped by mistake.
 3      * Recover the tree without changing its structure.
 4      * Could you devise a constant space solution?
 5      * using Morris Traversal
 6      * @param root
 7      */
 8     public void recoverTree(TreeNode root){
 9         if(root == null || root.left == null && root.right == null)
10             return ;
11         TreeNode pred1=null ;
12         TreeNode cur1=null ;
13         TreeNode pred2=null ;
14         TreeNode cur2=null ;
15         
16         TreeNode cur = root;
17         TreeNode last = null; // the last node that be printed out
18         
19         while(cur!=null){
20         
21             if(cur.left!=null){
22                 //find its predecessor
23                 TreeNode pre = cur.left;
24                 while(pre.right!=null && pre.right != cur){
25                     pre = pre.right;
26                 }
27                 if(pre.right == null)
28                 {
29                     pre.right = cur;//make the predecessor‘s right pointer points to the current node
30                     cur = cur.left;
31                 }else
32                 {
33                     pre.right = null;//recover the predecessor‘s right pointer.
34                     last = cur;
35                     cur = cur.right;// notice here!!!!!!
36                 }                
37                 
38             }else{
39                 last = cur;
40                 cur = cur.right;
41             }
42             //it‘s a very nice method!!!!
43             if(last!=null && cur != null && last.val>cur.val){
44                 if(pred1 == null){
45                     pred1 = last;
46                     cur1 = cur;
47                 }else
48                 {
49                     pred2 = last;
50                     cur2 = cur;
51                 }
52             }
53         }
54         
55         int temp ;
56         if(pred1 != null && cur2 !=null){
57             temp = pred1.val;
58             pred1.val = cur2.val;
59             cur2.val = temp;
60         }else{
61             temp = pred1.val;
62             pred1.val = cur1.val;
63             cur1.val = temp;
64         }
65         
66     }