[leetcode] 99.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?

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

题意：

一棵二叉树中有两个节点互相交换了位置，找出这两个节点。

思路：

1.我们知道二叉搜索树的中序遍历的结果是元素递增的排列，如果某两个元素交换了位置，那么就不会保证递增性。比方说原来下标为i，j的两个元素互相交换了位置即Ａ［ｉ］与Ａ［ｊ］互相交换了位置，那么现在A[i+1] < A[i], A[j] ＜Ａ［ｊ－１］，我们可以找到比前面元素小的两个元素即Ａ［ｉ＋１］，Ａ［ｊ］也即找到了Ａ［ｉ］，Ａ［ｊ］。采用递归的方法进行遍历，中间过程，只比较上一个元素。

以上。代码如下：

class Solution {
public:
    void recoverTree(TreeNode* root) {
        if (root == NULL)return;
        TreeNode* first = NULL, *second = NULL;
        TreeNode* last = new TreeNode(INT_MIN);
        recoverTree(root, first, second, last);
        if (first == NULL)return;
        swap(first->val, second->val);
    }
    void recoverTree(TreeNode* root, TreeNode* &first, TreeNode* &second, TreeNode*& last) {
        if (root == NULL)return;
        recoverTree(root->left, first, second, last);
        if (root->val < last->val) {
            if (first == NULL) {
                first = last;
                second = root;
            }
            else {
                second = root;
                return;
            }
        }
        last = root;
        recoverTree(root->right, first, second, last);
    }
};
           

2.之前使用递归的方式进行遍历，平均需要额外的空间复杂度是O(lgn)（递归的深度，最差可能是O(n))。采用Morris algorithm进行中序遍历，可以参考http://blog.csdn.net/u014673347/article/details/47974555

代码如下：

class Solution {
public:
    void recoverTree(TreeNode* root) {
        if (root == NULL)return;
        TreeNode* first = NULL, *second = NULL;
        TreeNode* last = new TreeNode(INT_MIN);
        TreeNode* prev = NULL, *curr = root;
        while (curr != NULL) {
            if (curr->left == NULL) {
                if (last->val > curr->val) {
                    if (first == NULL) {
                        first = last;
                        second = curr;
                    }
                    else{
                        second = curr;
                    }
                }
                last = curr;
                curr = curr->right;
            }
            else {
                prev = curr->left;
                while (prev->right != NULL && prev->right != curr)
                    prev = prev->right;
                if (prev->right == NULL) {
                    prev->right = curr;
                    curr = curr->left;
                }
                else {
                    if (last->val > curr->val) {
                        if (first == NULL) {
                            first = last;
                            second = curr;
                        }
                        else{
                            second = curr;
                        }
                    }
                    last = curr;
                    prev->right = NULL;
                    curr = curr->right;
                }
            }
        }
        if (first == NULL)return;
        swap(first->val, second->val);
    }
};