99. Recover Binary Search Tree.md

99. Recover Binary Search Tree

思路

注意到搜索树的特点：中序遍历是有序的。而题目说恰好有两个结点被交换，那么如果我们对其进行中序遍历，那应该基本上是有序的，局部不满足有序的地方就是我们要找的两个节点。即假设中序遍历序列是vec，找到两个不满足有序的地方：vec[i] > vec[i+1]，vec[j] > vec[j+1]，那么节点 i 和 j+1 就是我们要找的两个节点，注意 i = j 的特殊情况。

所以复杂度就是取决于中序遍历的复杂度，时间复杂度为O(N)，N为节点个数；空间复杂度一般也为O(H)，但可优化为O(1)。

方法一、常规方法

最简单的方法就是递归，用一个数组存放中序遍历结果，此时空间复杂度为O(H+N)，H为树高（即递归栈所用空间），N为节点个数。由于我们只需找到 i 和 j，所以其实可以不用存放整个遍历序列，空间复杂度优化成O(H)。

方法二、Morris遍历（常数空间复杂度）

morris遍历的核心思想是利用叶子节点的大量空闲指针，实现空间开销的极限缩减。

要使用O(1)空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（因为不能用栈作为辅助空间）。为了解决这个问题，Morris方法用到了线索二叉树（threaded binary tree）的概念，利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。以中序遍历为例：将左子树最右节点的右空闲指针在遍历中途指向根节点（根节点是左子树最右节点在中序遍历序列中的后继），当我们再次遍历到这个节点时，发现其有右孩子，就表示原根节点的左子树访问完毕，此时就可以访问根节点了。具体程序如下：

从根节点开始访问：
1）如果当前节点 p 不存在左子树，按中序遍历规则，访问 p 并进入其右子树进行遍历。
2）如果当前节点 p 存在左子树，就找到 p 的前驱节点（即左子树中的最右节点），并将其的右孩子指向 p，同时当前节点转入左子树进行遍历。
注意（2）中访问右子树时，如果节点本身没有右子树，则会直接转入其后继节点 p，此时 p 的左子树遍历完成。为了还原树结构，我们需要重新找到 p 的前驱节点，并将其右孩子设置为空。之后我们访问节点p，并进入其右子树进行遍历。

C++

方法一、常规方法

class Solution {
private:
    vector<TreeNode*>vec; // 存放中序遍历的结果
    void midVisit(TreeNode* root){
        if(!root) return;
        midVisit(root -> left);
        vec.push_back(root);
        midVisit(root -> right);
    }
public:
    void recoverTree(TreeNode* root) {
        if(!root) return;
        midVisit(root);

        vector<int>tmp;
        for(int i = 0; i < vec.size() - 1; i++){
            if(vec[i]->val > vec[i+1]->val) tmp.push_back(i);
        }

        int i = tmp[0];
        int j = tmp.size() == 1 ? tmp[0]: tmp[1];

        int tmp_val = vec[i] -> val;
        vec[i] -> val = vec[j+1] -> val;
        vec[j+1] -> val = tmp_val;
    }
};

方法二、Morris遍历（常数空间复杂度）

class Solution {
private:
    TreeNode *p = nullptr, *pre = nullptr;
    TreeNode *node_i = nullptr, *node_j = nullptr; // node_i和node_j是需要交换的节点
    void visit(){ // 访问函数
        if(pre && pre -> val > p -> val){
            if(!node_i) node_i = pre;
            node_j = p; 
        }
        pre = p;
        p = p -> right;
    }
public:
    void recoverTree(TreeNode* root) {
        if(!root) return;

        // Morris中序遍历算法: 能将非递归的中序遍历空间复杂度降为 O(1)
        p = root;
        while(p){
            if(p -> left == nullptr){ // 无左孩子, 访问即可
                visit();
            } 
            else{ // 有左孩子
                TreeNode* p_back = p;
                p = p -> left;
                while(p -> right && p -> right != p_back) p = p -> right; // 找到左子树上最右的节点
                if(!(p -> right)){ // 左子树最右节点的右子树为空
                    p -> right = p_back;
                    p = p_back -> left;
                }else{ //  左子树最右节点的右子树不为空, 说明左子树已访问
                    p -> right = nullptr;
                    p = p_back;
                    visit();
                }
            }
        }

        int tmp_val = node_i -> val;
        node_i -> val = node_j -> val;
        node_j -> val = tmp_val;
    }
};