Recover Binary Search Tree

对于一个Binary Search Tree来说, 按照inOrder的顺序visit各个节点就会是从小到大的排列.
因为有两个节点放错了,所以会出现两次前面的点的值大于后面的点.
用三个指针, 第一个指针pre, 用来遍历整个Tree; 第二个指针first, 用来标记第一个错误的点; 第三个指针second, 用来标记第二个错误的点.

Note:在递归的时候, 何时给pre赋值, 何时给first赋值都是容易bug的地方. 说白了pre就是一个带头的, 发现一个不对的点就标记一下. (第一个点: 它的值比该层递归的root值大, 这个点不对; 第二个点, 当它作为root的时候, 位于前面的点比他大, 就是这个root有问题, 标记为second)

 public class Solution {  
   TreeNode pre;  
   TreeNode first;  
   TreeNode second;  
   public void recoverTree(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root);  
     int tmp = first.val;  
     first.val = second.val;  
     second.val = tmp;  
   }  
   public void inOrder(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root.left);  
     if (pre == null) {  
       pre = root;  
     }else {  
       if (pre.val > root.val) {  
         if (first == null) {  
           first = pre;  
         }
         second = root;  // 这里会发现, 如果出现了异常, second会一直跟着root走.直到不再出现异常为止,
                         // 这个时候second也就指向了第二个异常的点了.注意: second不是等于pre!!!!
       }  
       pre = root;  
     }  
     inOrder(root.right);  
   }  
 }  

上面是优解,下面这个方法虽然不是最优解, 但是容易上手. 将BST按照inorder顺序把节点和节点的数值存到两个list中, 将节点值list sort一下, 重新赋值给各个节点.

 public class Solution {  
   public void recoverTree(TreeNode root) {  
          if (root == null)  
            return;  
          ArrayList<TreeNode> visit = new ArrayList<TreeNode>();  
          ArrayList<Integer> values = new ArrayList<Integer>();  
          inOrder(visit, values, root);  
          Collections.sort(values);  
          for (int i=0; i<values.size(); i++) {  
            TreeNode curr = visit.get(i);  
            curr.val = values.get(i);  
          }  
        }  
   public void inOrder(ArrayList<TreeNode> visit, ArrayList<Integer> values, TreeNode node) {  
     if (node == null)  
       return;  
     inOrder(visit, values, node.left);  
     visit.add(node);  
     values.add(node.val);  
     inOrder(visit, values, node.right);  
   }  
 }