小旭讲解 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.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

• A solution using O(n) space is pretty straight forward.
• Could you devise a constant space solution?

Accepted

视频讲解

B站视频源

YouTube视频源

如果大家有兴趣一起侃侃数据结构与算法，那么可以通过下面的微信号或者微信公众号给我留言（要带上自己的微信ID哦）：
微信公众号（推荐）：ihuxublog（胡小旭博客）
微信：genialx
如果你喜欢我的视频，可以到B站或者Youtube关注我~

分析题目

解法一 排序

考虑将错误的二叉树进行一次中序遍历，并将遍历的结果保留到数组中。然后将问题转换成在一个线性数组中查找错误的两个元素的值。最后，再遍历一次二叉搜索树进行恢复即可。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int x = -1, y = -1;
    void inorder(TreeNode* node, vector<int>& nums) {
        if (node == nullptr) return;
        inorder(node->left, nums);
        nums.push_back(node->val);
        inorder(node->right, nums);
    }
    // 1 2 3 4 5
    // 1 3 2 4 5
    // 1 4 3 2 5
    void findTwoSwappedNums(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                y = nums[i + 1];
                if (x == -1) x = nums[i];
                else break;
            }
        }
    }
    void recover(TreeNode* node) {
        if (node == nullptr) return;
        if (node->val == x) {
            node->val = y;
        } else if (node->val == y) {
            node->val = x;
        }
        recover(node->left);
        recover(node->right);
    }
public:
    void recoverTree(TreeNode* root) {
        vector<int> nums{};
        inorder(root, nums);
        findTwoSwappedNums(nums);
        recover(root);
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

解法二

即在递归中序遍历二叉搜索树时，利用前驱节点，及时的判断当前节点与前驱节点相对关系的合法性，并将错误的节点保留下来。最后，交换两个错误的节点中的值。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *x = nullptr, *y = nullptr, *pred = nullptr;
    void inorder(TreeNode* node) {
        if (node == nullptr) return;
        inorder(node->left);
        if (pred != nullptr && node->val < pred->val) {
            y = node;
            if (x == nullptr) x = pred;
            else return;
        }
        pred = node;
        inorder(node->right);
    }
public:
    void recoverTree(TreeNode* root) {
        inorder(root);
        int tmp = x->val;
        x->val = y->val;
        y->val = tmp;
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(\log n)

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-explain-leetcode-99-recover-binary-search-tree/