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实现后果
欢送关注
公众号【书所集录】