Recover Binary Search Tree

Q：
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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

A：
------------in-Order search--- and find the two that are not ordered.-------------------
----------------哎，找到之后， 交换值和字节点的值就是了。 ----------非要找parent节点干啥？？？-----------想不开---------------------------------
由于对于balanced tree， 每个节点找其pre 和next node， 总的复杂度还是 O（n），因此，代码如下。

public class Solution {
    TreeNode[] swap2;
    public void recoverTree(TreeNode root) {
        helper(root);
        // swap the values of the two node
        int tmp = swap2[0].val;
        swap2[0].val = swap2[1].val;
        swap2[1].val = tmp;
    }
    private void helper(TreeNode root){
        if(root ==null)
            return;
        helper(root.left);
        TreeNode preNode=null, nextNode=null;
        if(root.left != null)
            preNode = getMax(root.left);
        if(root.right != null)
            nextNode = getMin(root.right);
        if(preNode != null && preNode.val > root.val){
            if(swap2 == null){
                swap2 = new TreeNode[2];
                swap2[0] = preNode;
            }
            swap2[1] = root;
        }
        if(nextNode != null && root.val > nextNode.val){
            if(swap2 == null){
                swap2 = new TreeNode[2];
                swap2[0] = root;
            }
           swap2[1] = nextNode;
        }
        helper(root.right);
    }
    private TreeNode getMin(TreeNode root) {
        // get the minimum value of a tree
        while(root!=null && root.left != null)
            root = root.left;
        return root;
    }
    private TreeNode getMax(TreeNode root) {
        // get a maximum value of a tree
        while(root != null && root.right!=null)
            root = root.right;
        return root;
    }
}

另外，由于错误2 的原因，是因为我们用了 static.因此，在我们真正实现的时候，我们用了    swap2[] 数组，作为参数来记录更改的变量。


Mistakes:1:  当收入的inoerder list 为： 1 4 3 2 5 6 的时候，如果我们仅仅是两两比较， 就会首先记录 4 3 ;
然后查看3 ,2 记录下了3。  可是，这个时候，我们需要记录的是 2.
方法是： 当已经找到第一个的时候，我们就应该找第二个的时候，就要找后面的那个。因此，对比3,2的时候，我们就应该记录2.


2：  ？？？？？下面这个，估计是leetcode的编译错误。

Input:	{2,#,1}
Output:	{2,#,0}
Expected:	{1,#,2}

在Eclipse上是正确的。

3:  对于 root 和right 的对比， 应该先比较root 和first of root.right，来建设swap2[] 数组。


Learned:
----------------------------利用同样的思路， 但是，利用同一个地址的引用，我们可以把代码精简如下------------其实就是把一个root节点的前后的对比，巧妙地分成了利用preNode的一个对比。

public class Solution {
    TreeNode preNode = null;

    public void recoverTree(TreeNode root) {
        // use in-order traverse
        TreeNode[] swap2 = new TreeNode[2];
        // use recursively in-order,
        // remember the places that lastAdded.val>curNode.val
        inOrder(root, swap2);
        // swap value
        int tmp = swap2[0].val;
        swap2[0].val = swap2[1].val;
        swap2[1].val = tmp;
    }

    private void inOrder(TreeNode root, TreeNode[] swap2) {
        if (root == null)
            return;
        inOrder(root.left, swap2); // the preNode would be changed ---
                                    // to last node of root.left
        if (preNode != null && preNode.val > root.val) {
            if (swap2[0] == null) 
                swap2[0] = preNode;
            swap2[1] = root;
        }
        preNode = root;
        inOrder(root.right, swap2);
    }
}

错误：
1：  （不知道为什么？？？哈哈，别逗了，Tiger， BS 你)，
     preNode如果作为函数传递的话，是不对的。必须得作为向量。

---------------------------------3 rd pass---------

public class Solution {
    static TreeNode justPrinted ,node1=null, node2 = null;
    public void recoverTree(TreeNode root) {
        inOrder(root);
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
    private void inOrder(TreeNode root){
        if(root == null)
            return ;
        inOrder(root.left);
        if(justPrinted !=null &&  justPrinted.val>root.val){
            if(node1==null)
                node1 = justPrinted;
            node2 = root;
        }
        justPrinted = root;
        inOrder(root.right);
    }
}

-----------------上面的代码是会报错的， 但只需要把第二行的 static 去掉，就可以了。  不知道为什么？