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?

思路：BST就是对应的InOrder，1) 那么只需要InOrder，维持一个当前的Val，然后看下一个是不是比当前的大，如果不大，则记录位置，直到找到2个位置first 和 second，最后交换就可以  2) 不管O(n) space constraits的话，可以用一个数组保存遍历出来的 val,一个保存出来的 pointer,然后排序val数组，再全部给pointer赋值就OK.思路1的话，递归或者非递归都OK。

        如果是O(1)的space呢？That's MorrisInOrder.

class Solution {public:    void recoverTree(TreeNode *root) {        if (!root){            return;        }        /**        {68,41,#,-85,#,-73,-49,-98,#,#,#,-124}    ==> {68,41,#,-73,#,-85,-49,-98,#,#,#,-124}        {1,2,3} => {2,1,3}                first是找到第一个失配的pair 
     
       的pre : pre->val < current->val        second是找到最后一个失配的pair
      
        的current : pre->val < current->val        当然，first和second可能相等        因为先访问到，first是大的，那么说明争取的位置不在这里        后访问到,second是小的，说明正确的位置也不在这里,永远都是相邻的pair，记住第一个pair的头和最后一个pair的尾巴                   8                /    \               5       10             /   \    /      我们只需要找到9和2的位置，然后swap就ok, (9,3) 的first  (8,2)的second.            3      6  |2|               / \     \         |9|  4     7                 另一种视角：|9| 3 4 5 6 8 |2| 10   需要变成：                   2  3 4 5 6 8  9  10                  遍历的时候，记住<9,3>的first和<8,2>的second                最后swap(first->val,second->val)          */                TreeNode * first = NULL, *second = NULL;        TreeNode * current = root;        TreeNode * prev = NULL, *prev2 = NULL;                while(current){            if (!current->left){                //visit first指向第一个不符合的prev结点                //second指向不符合的second结点                if (prev && current->val < prev->val){                    if (!first){                        first = prev;                    }                    second = current;                }                prev = current;    //prev指针forward                current = current->right;                continue; //注意的这个continue不能丢掉            }            TreeNode * p = current->left;            while(p->right && p->right != current){                p = p->right;            }            if (!p->right){ //threading                p->right = current;                current = current->left;            }            //注意这里threading的时候，prev肯定不可能是空的            if (p->right == current){ //unthreading                //vist                if (current->val < prev->val){                    if (!first){                        first = prev;                    }                    second = current;                }                prev = current; //prev指针forward                p->right = NULL;                current = current->right;            }        }        if (first && second){            swap(first->val,second->val);            return;        }    }};