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

进阶:

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

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

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

假设有一个递增的序列 [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 算法，并且也进一步描述了这个算法的信息。如果有兴趣了解的话，可以从下方的链接入口继续了解。

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