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

Tips 2020-08-08

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 > 23 > 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

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

欢迎关注


公众号 【书所集录

相关推荐