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的中序遍历结果中，第一个出错的数一定比它后面的数大，第二个出错的数一定比它前面的小（关键：有可能两个数相邻，也有可能两个数不相邻，不相邻的时候second被更新两次）。

解法一（递归）：

TreeNode* pre = NULL;
    TreeNode* first = NULL;
    TreeNode* second = NULL;
    void recoverTree(TreeNode* root) {
        dfs(root);
        swap(first -> val, second -> val);
    }
    void dfs(TreeNode* root) {
        if(!root) return ;
        dfs(root -> left);
        if(pre && pre -> val > root -> val){
            if(!first) 
                first = pre;
            second = root;
        }
        pre = root;
        dfs(root -> right);
    }

解法二（开辟栈空间辅助中序遍历）：

void recoverTree(TreeNode* root) {
        TreeNode* p = root;
        TreeNode* pre = NULL;
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        stack<TreeNode*> st;
        while(!st.empty() || p){
            if(p){
                st.push(p);
                p = p -> left;
            }
            else{
                p = st.top();
                st.pop();
                if(pre && pre -> val > p -> val){
                    if(first == NULL)
                        first = pre;
                    second = p;
                }
                pre = p;
                p = p -> right;
            }
        }
        swap(first -> val, second -> val);
    }

解法三（Morris Traversal）：
注：Morris Traversal会改变树的结构，要注意恢复原来的结构。

void recoverTree(TreeNode* root) {
        TreeNode *cur = root, *tmp = NULL;
        TreeNode *pre = NULL;
        TreeNode *first = NULL, *second = NULL;
        while(cur){
            if(pre && pre -> val > cur -> val){
                 if(first == NULL)
                    first = pre;
                second = cur;
            }
            if(cur -> left){
                tmp = cur -> left;
                while(tmp -> right && tmp -> right != cur)
                    tmp = tmp -> right;
                if(tmp -> right == cur){
                    tmp -> right = NULL;                   
                    pre = cur;
                    cur = cur -> right;
                }
                else{
                    tmp -> right = cur;
                    cur = cur -> left;
                }
            }
            else{
                pre = cur;
                cur = cur -> right;
            }
        }
        swap(first -> val, second -> val);
    }

参考资料：
https://leetcode.com/problems/recover-binary-search-tree/discuss/32562/Share-my-solutions-and-detailed-explanation-with-recursiveiterative-in-order-traversal-and-Morris-traversal