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 算法，并且也进一步描述了这个算法的信息。如果有兴趣了解的话，可以从下方的链接入口继续了解。
那么在这里，笔者就仅使用 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
实现结果
欢迎关注
公众号 【书所集录】
