99. 恢复二叉搜索树

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-binary-search-tree

题目

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
     2

输出: [3,1,null,null,2]

   3
  /
 1
     2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / 1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / 1   4
   /
  3

进阶:

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

解题思路

思路：中序遍历（递归），Morris算法

题目中说明，二叉搜索树中的两个节点被错误地交换，需要在不改变结构的情况下恢复二叉搜索树。

我们知道，使用中序遍历二叉搜索树时，得到的序列必然是递增的。如果二叉搜索树的节点被错误交换，那么使用中序遍历，就能够定位到错误的节点。

假设有一个递增的序列 [1, 2, 3, 4]，如果我们交换相邻的位置，比如 2 和 3，那么序列就会变为 [1, 3, 2, 4]。此时，这里会出现一处错误点，因为 3 > 2 不满足序列递增。如果我们交换不相邻的位置，例如 1 和 4，那么序列就会变为 [4, 2, 3, 1]，此时，会出现两个错误点，4 > 2 和 3 > 1 不满足序列递增。

这里，我们可以判断，当两个节点被错误交换时，最多会产生两处错误。

这里额外提及下，因为前面给的例子，是先给定的递增序列，我们假设取交换两个节点。但如果给的是已经交换的节点，如何将节点恢复至正确的位置。从上面假设的分析中，我们可以看到，如果是相邻的节点被交换，那么我们只要再次交换两个节点即可；但如果不是相邻节点被交换，我们可以发现，两处错误点，只要将前面第一处错误的左边节点，与后面第二处错误的右边节点交换，即可恢复。

在这里，我们能直接想到的就是，利用一个数组，去存储使用中序遍历二叉搜索树的值序列，只要能够找到错误的地方，就能够将其更正。

中序遍历（递归）

但这里，我们不使用额外的数组去存储使用中序遍历二叉搜索树的值序列。因为前面根据分析能够判断，当两个节点被错误交换，最多会出现两个错误。那么我们只要关心中序遍历的值序列每个相邻的位置大小是否不对。下面是具体的算法（使用中序遍历访问）：

在遍历访问的过程中，用变量 pre_node 记录当前遍历的最后一个节点。
当进行下个节点的遍历时，用当前节点的值与 pre_node 节点的值进行比较。如果 pre_node.val >= cur_node.val，也就说明当前位置出错。
继续向下遍历，若能找到第二处位置时，可以直接结束遍历。
当确定错误的位置时，将节点值进行交换。

在这里，我们用递归来实现这个算法。具体代码见【代码实现 # 中序遍历（递归）】

注意： 这个算法，在最差的情况下，也就是需要交换的位置出现在树的最右侧的叶子节点中，那么这个算法同样还是会遍历整个二叉搜索树。

Morris 算法

在题目进阶处提及，是否能够实现常数时间复杂度的算法。在官方题解中提及的就是 Morris 算法，并且也进一步描述了这个算法的信息。如果有兴趣了解的话，可以从下方的链接入口继续了解。

https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/

那么在这里，笔者就仅使用 Morris 的思想去尝试解决该问题，就不再额外展开描述。

具体的代码见【代码实现 # Morris 算法】

代码实现

# 中序遍历（递归）
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # 用 pre_node 记录遍历的最后一个节点
        self.pre_node = TreeNode(float(‘-inf‘))
        # 用来标记两个错误
        self.first_error_node = None
        self.second_error_node = None
        self.count = 0

        def in_order(root):
            if not root:
                return None
            in_order(root.left)
            # 比较 pre_node 值与当前节点的值
            if self.pre_node.val >= root.val and self.first_error_node == None:
                # 如果 pre_node >= root.val 表示此处出错,进行记录
                self.first_error_node = self.pre_node
            if self.pre_node.val >= root.val and self.first_error_node:
                # 这里标记第二处错误，无论是出现一次错误还是两次错误都适用
                self.second_error_node =  root
                # 出现两次可以终止
                self.count += 1
                if self.count == 2:
                    return
            # 维护 pre_node
            self.pre_node = root
            in_order(root.right)
        
        in_order(root)
        # 交换节点
        self.first_error_node.val, self.second_error_node.val = self.second_error_node.val, self.first_error_node.val

# Morris 算法
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        first_error = None
        second_error = None
        pre_node = TreeNode(float(‘-inf‘))
        predecessor = None

        while root:
            if root.left:
                predecessor = root.left
                # 当节点有左孩子时，找到当前节点的最右的节点
                while predecessor.right and predecessor.right != root:
                    predecessor = predecessor.right
                
                # 如果 predecessor 节点的右孩子为 None，将右指针指向 root，然后遍历左子树
                if predecessor.right == None:
                    predecessor.right = root
                    root = root.left
                # 若 predecessor 节点的右孩子不为空，同样将指针指向 root
                # 同时说明左子树遍历完成，置空 predecessor 右孩子，访问 root 的右孩子
                else:
                    # 没有左孩子，直接访问右孩子
                    if pre_node.val >= root.val and first_error == None:
                        first_error = pre_node
                    if pre_node.val >= root.val and first_error:
                        second_error = root
                    pre_node = root
                    # 置空 predecessor
                    predecessor.right = None
                    root = root.right
            else:
                # 没有左孩子，直接访问右孩子
                if pre_node.val >= root.val and first_error == None:
                    first_error = pre_node
                if pre_node.val >= root.val and first_error:
                    second_error = root
            
                pre_node = root

                root = root.right
        
        first_error.val, second_error.val = second_error.val, first_error.val

实现结果

LeetCode 99. 恢复二叉搜索树 | Python

欢迎关注

公众号【书所集录】