88006613779abeeea7a95aae25200d55
(难度Hard) Problem 99. Recover Binary Search Tree(恢复BST)

Recover Binary Search Tree

Difficulty

Hard

Description

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?

题意

给定一个被交换过其中两个元素的二叉搜索树,要求还原出原树

题解

这道题是Hard难度,刚拿到手上的确很难,一筹莫展。我想了很久,也没有思路,因为可能出现的情况太多了。单单是样例当中的两个例子,就很难判断。

后来经过思考才发现,是因为有一个关键点没有想到。这题的所有解法都是围绕这个关键点展开的。

在上一题当中我们判断一棵二叉搜索树的时候,其实用到了这个方法。那就是中序遍历。

我们都知道二叉树的中序遍历,其实就是用递归方法来遍历树。就是我们每次遇到一个节点都先去遍历它的左子树,等它所有的左子树都遍历完了,我们再获取它本身的元素,最后再去遍历它的右子树。

中序遍历看似比较平常,但是和二叉搜索树的性质结合起来,就不一般了。

二叉搜索树什么性质呢?我们也都知道,二叉搜索树当中每个节点的左子树的元素都小于它,而右子树的元素都大于它。

那如果我们使用中序遍历的方法来遍历一棵二叉搜索树会发生什么呢?

答案很简单,我们将会得到一个升序的序列

这就是本题的关键,升序的序列有了,我们就很容易找到顺序发生错乱的两个数。找到这两个数之后,我们只需要把它们在二叉搜索树当中的值交换就行了。

代码:

```c++
class Solution {
public:
// 中序遍历
void inorder(vector& vt, TreeNode* node) {
if (node == nullptr) return ;
if (node->left != nullptr) {
inorder(vt, node->left);
}
vt.push_back(node->val);
if (node->right != nullptr) {
inorder(vt, node->right);
}
}

// 还原二叉搜索树,其实原理很简单,就是遍历树,找到等于x的位置赋值成y,找到等于y的位置赋值成x
// 因为二叉搜索树当中不会有重复的元素,所以修复完成之后就可以return了
void recover(TreeNode* node, int num, int x, int y) {
    if (num == 0 || node == nullptr) return ;
    if (node->val == x || node->val == y) {
        node->val = node->val == x ? y : x;
        num--;
    }
top Created with Sketch.