Recover Binary Search Tree

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?

Naive Way:O(1)的做法我实在是想不出来，明明inorder traversal 就要O(n) space了。

这是O(n) space 的做法，这样做比较无脑，任何错误都可以纠正。

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public void recoverTree(TreeNode root) {  
     List<Integer> vals = new ArrayList<Integer>();  
     List<TreeNode> nodes = new ArrayList<TreeNode>();  
     inorder(root, nodes, vals);  
     Collections.sort(vals);  
     for(int i = 0;i < nodes.size();i++)  
       nodes.get(i).val = vals.get(i);  
   }  
   private void inorder(TreeNode root, List<TreeNode> nodes, List<Integer> vals){  
     if(root==null) return;  
     inorder(root.left, nodes, vals);  
     nodes.add(root);  
     vals.add(root.val);  
     inorder(root.right, nodes, vals);  
   }  
 }  

Improved Way: 原来还有一个叫Morris Threading Traversal 的东西。这里有一个blog，是一个中国人专门写Morris Traversal的，http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html，非常有用。线索二叉树。

针对这道题，Morris Traversal 解决了用O(1)的space遍历BST，但是找到错误交换的两个点依然是一个问题。肯定是在Morris Traversal的算法上修改。先把Morris Traversal的算法列出来。

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public void morrisTraversal(TreeNode root){  
     TreeNode temp = null;  
     while(root!=null){  
       if(root.left!=null){  
         // connect threading for root  
         temp = root.left;  
         while(temp.right!=null && temp.right != root)  
           temp = temp.right;  
         // the threading already exists  
         if(temp.right!=null){  
           temp.right = null;  
           System.out.println(root.val);  
           root = root.right;  
         }else{  
           // construct the threading  
           temp.right = root;  
           root = root.left;  
         }  
       }else{  
         System.out.println(root.val);  
         root = root.right;  
       }  
     }  
   }   

两个加粗部分对应遍历时的输出顺序，所以找出错误交换的节点也应该是在这里修改。如何修改？因为MorrisTraversal得到的应该是升序的，所以前一个大于后一个说明前一个一定是错的，为什么不是后一个是错的呢？因为后一个比前一个小说明后一个应该被先遍历到，前一个节点至少应该是后一个节点那么大小。而一旦找到了第一个错误的节点，第二次再遇到前一个大于后一个的时候，错误的就是后一个了。为什么呢？因为我们知道了第一个错误的节点是value大于它本来的value，所以我们现在要找的就是value小于它本来value的节点，因为这个节点本来应该是第一个错误的节点所在的位置。
而当出错的是连续两个节点时，可能只检测到一个非升序情况，因为连着的这两个是错的。这时要暂时另第二个错误节点等于第一个后面的节点。

所以要做的就是把  
System.out.println(root.val);
替换成
if(pre!=null && pre.val > root.val){
      if(first==null){first = pre;second = root;}
      else{second = root;} 
}
pre = root;  

这里非常好理解，因为原来是按照System.out.println(root.val)的顺序输出的，也就是说该位置得到的每一次root值都是排好序的，那么将上一次的root作为这一次的pre就是按照顺序的pre和root，如果二者大小关系不对，可知错误节点在此处。

 public void recoverTree(TreeNode root) {  
     TreeNode pre = null;  
     TreeNode first = null, second = null;  
     // Morris Traversal  
     TreeNode temp = null;  
     while(root!=null){  
       if(root.left!=null){  
         // connect threading for root  
         temp = root.left;  
         while(temp.right!=null && temp.right != root)  
           temp = temp.right;  
         // the threading already exists  
         if(temp.right!=null){  
           if(pre!=null && pre.val > root.val){  
             if(first==null){first = pre;second = root;}  
             else{second = root;}  
           }  
           pre = root;  
           temp.right = null;  
           root = root.right;  
         }else{  
           // construct the threading  
           temp.right = root;  
           root = root.left;  
         }  
       }else{  
         if(pre!=null && pre.val > root.val){  
           if(first==null){first = pre;second = root;}  
           else{second = root;}  
         }  
         pre = root;  
         root = root.right;  
       }  
     }  
     // swap two node values;  
     if(first!= null && second != null){  
       int t = first.val;  
       first.val = second.val;  
       second.val = t;  
     }  
   }