题目描述（困难难度）

依旧是二分查找树的题，一个合法的二分查找树随机交换了两个数的位置，然后让我们恢复二分查找树。不能改变原来的结构，只是改变两个数的位置。二分查找树定义如下：

解法一 递归

和 98 题有些像。这里的思路如下：

让我们来考虑交换的位置的可能：

  1. 根节点和左子树的某个数字交换 -> 由于根节点大于左子树中的所有数，所以交换后我们只要找左子树中最大的那个数，就是所交换的那个数

  2. 左子树和右子树的两个数字交换 -> 找左子树中最大的数，右子树中最小的数，即对应两个交换的数

  3. 左子树中的两个数字交换
  4. 右子树中的两个数字交换

思想有了，代码很好写了。

解法二

如果记得 98 题，我们判断是否是一个合法的二分查找树是使用到了中序遍历。原因就是二分查找树的一个性质，左孩子小于根节点，根节点小于右孩子。所以做一次中序遍历，产生的序列就是从小到大排列的有序序列。

回到这道题，题目交换了两个数字，其实就是在有序序列中交换了两个数字。而我们只需要把它还原。

交换的位置的话就是两种情况。

  • 相邻的两个数字交换

    [ 1 2 3 4 5 ] 中 2 和 3 进行交换，[ 1 3 2 4 5 ]，这样的话只产生一组逆序的数字（正常情况是从小到大排序，交换后产生了从大到小），3 2。

    我们只需要遍历数组，找到后，把这一组的两个数字进行交换即可。

  • 不相邻的两个数字交换

    所以我们只需要遍历数组，然后找到这两组逆序对，然后把第一组前一个数字和第二组后一个数字进行交换即完成了还原。

所以在中序遍历中，只需要利用一个 pre 节点和当前节点比较，如果 pre 节点的值大于当前节点的值，那么就是我们要找的逆序的数字。分别用两个指针 first 和 second 保存即可。如果找到第二组逆序的数字，我们就把 second 更新为当前节点。最后把 first 和 second 两个的数字交换即可。

中序遍历，参考 ，有三种方法，递归，栈，Morris 。这里的话，我们都改一下。

因为之前这个方法中用了 pre 变量，为了方便，这里也需要 pre 变量，我们用 pre_new 代替。具体 Morris 遍历算法参见 94 题 。利用 Morris 的话，我们的空间复杂度终于达到了 O（1）。

总

自己开始看到二分查找树，还是没有想到中序遍历，而是用了递归的思路去分析。可以看到如果想到中序遍历，题目会简单很多。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情