小旭讲解 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关注我~

分析题目

小旭讲解 Recover Binary Search Tree
小旭讲解 Recover Binary Search Tree

解法一 排序

小旭讲解 Recover Binary Search Tree
小旭讲解 Recover Binary Search Tree

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

代码

/**
 * 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)

解法二

小旭讲解 Recover Binary Search Tree
小旭讲解 Recover Binary Search Tree
小旭讲解 Recover Binary Search Tree
小旭讲解 Recover Binary Search Tree

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

代码

/**
 * 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/
最后修改日期:2019年11月25日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。