[数据结构与算法]99 恢复二叉搜索树

题目

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

• 分析
  • 如正常的二叉搜索树中序遍历后的序列为1、2、3、4、5、6
  • 交换2和6，则错误交换后的二叉搜索树为1、6、3、4、5、2.有两个逆序对，分别为6和3(ai>ai+1)以及5和2(aj>aj+1)
  • 交换2和3，则错误交换后的二叉搜索树为1、3、2、4、5、6.有一个逆序对为3和2(ai>ai+1)
  • 解题方法
    • 寻找中序遍历序列中的逆序对
    • 如果有两个，记为ai和aj且ai>ai+1, aj>aj+1，对应的交换节点为ai和aj+1.记x为ai，y为aj+1.
    • 如果有一个，记为ai,对应的交换节点为ai和ai+1。记x为ai,y为ai+1.
    • 交换x和y的值,x和y对应四个元素中两端的两个元素。
• 三种实现对应三种方法，依次优化
  • 方法一：开辟一个新数组num记录中序遍历序列，线性遍历找到x和y，交换二者的位置。
    • 时间复杂度O(n)
    • 空间复杂度O(n)
  • 方法二：使用辅助栈得到中序遍历序列，在遍历中找到x和y交换二者位置。
    • 时间复杂度O(n)
    • 空间复杂度O(n)
  • 方法三：morris算法，在得到中序遍历序列的同时，找到x和y交换二者的位置。
    • 时间复杂度O(n)
    • 空间复杂度O(1)
• 方法一：迭代+向量储存中序遍历序列

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> nums;//记录中序遍历的结果
        TreeNode *x = NULL, *y = NULL;//记录要交换的两个节点
        inordertraverse(nums, root);
        int size = nums.size();
        for(int i=0; i<size; i++){
        	//寻找逆序对，只会出现最多两个逆序对
            if(i+1<size && nums[i]->val>nums[i+1]->val){
                y = nums[i+1];
                if(x==NULL) x = nums[i];
                else break;
            }
        }
        swap(x->val,y->val);
    }
    void inordertraverse(vector<TreeNode*>& nums, TreeNode* root){
        if(root == NULL) return;
        inordertraverse(nums, root->left);
        nums.push_back(root);
        inordertraverse(nums, root->right);
    }
};

• 方法二：栈+双指针记录要交换节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode *pre = NULL, *cur = root;//pre为当前节点中序遍历序列中的前驱，cur为当前节点
        TreeNode* x = NULL, *y = NULL;//寻找两个要交换的节点
        //栈模拟递归得到中序遍历序列
        while(cur!=NULL || !stk.empty()){
            if(cur!=NULL){
                stk.push(cur);
                cur = cur->left;
            }else{
                cur = stk.top();
                stk.pop();
                if(pre!=NULL && pre->val>cur->val){//找到逆序对，最终x和y为四个节点中两端的两个
                    y = cur;
                    if(x == NULL) x = pre;
                    else break;
                    }
                }
                pre = cur;//记录此时的cur
                cur = cur->right;//cur转向当前节点的右孩子
            }
        }
        swap(x->val, y->val);
    }
};

• 方法三：morris+双指针记录要交换节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *x = NULL, *y = NULL;
        TreeNode *cur = root, *pre = NULL;
        while(cur!=NULL){
            if(cur->left == NULL){//如果没有左孩子表示到达了最左端节点，访问该节点
                if(pre != NULL && pre->val > cur->val){
                    y = cur;
                    if(x == NULL) x = pre;
                }
                pre = cur;
                cur = cur->right;
            }else{//如果当前节点有左孩子，找到它左子树的最右端节点，处理线索
                TreeNode *node = cur->left;
                while(node->right!=NULL && node->right!=cur)
                    node = node->right;
                if(node->right==NULL){//没有设置线索
                    node->right = cur;
                    cur = cur->left;
                }else{//删除线索并处理此时的cur
                    if(pre!=NULL && pre->val > cur->val){
                        y = cur;
                        if(x == NULL) x = pre;//与前两种做法不同的是，此时不能用break
                        //此时退出的话并没有将线索完全删除，在输出结果时遍历二叉树会出错
                    }
                    node->right = NULL;
                    pre = cur;
                    cur = cur->right;
                }
            }
        }
        swap(x->val,y->val);
    }
};

参考详解