刷起来 99 ～ 恢复 BST

基本信息

• 题号：99
• 题厂：未知（如有题友知道题厂信息来源，请麻烦告知，感谢）
• 难度系数：中

有一个 Binary Search Tree（BST），有两个节点的 value 值被置换了。请把这两个节点找出来再换回来，让树回归成一个合格的 Binary Search Tree（BST）

如图所示，1-3-2 的 BST 中，1-3 两个节点放反了，对换以后变成 3-1-2 满足 BST 的编排需求 。

root = [1,3,null,null,2]
[3,1,null,null,2]

解题思路

这道题看似很玄幻，其实深入理解 BST 节点编排原理后，算法逻辑还是挺简单的🙈。

BST（Binary Search Tree）：BST 是一种特殊的二分树，在 BST 中，一个节点左边的所有节点都比该节点小；一个节点右边的所有节点都要比该节点大……

• 了解了 BST 左右节点位置编排原理后，我们发现，如果将一个 BST 按 inorder 遍历，遍历出来的各节点 value 值输出顺序必然是按升序排列的。
• 换句话说，在节点数量一致，各节点 value 值一致的情况下，要满足节点成型 BST，无论谁做 root 节点，按照 inorder 遍历结果一定是各节点 value 值由小到大排列……

例如：有 3 个节点，value 值分别是 1， 2， 3.

• 如果选择 1 做根节点，那 2 和 3 只能当 1 的右节点
• 如果选择 2 做根节点，那 1 只能在 2 的左边，3 必然在 2 的右边才能满足 BST 的编排要求

无论 1 和 2 谁做根节点构造出来的 BST，按照 inorder 顺序遍历，输出一定是 1-2-3……

• 题目已知就两个节点放反了，所以我们把题目已知的 BST 按 inorder 遍历后，找出那两个没有按升序排列的节点，对换一下就可以了。

# 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: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # 初始化一个 temp 存放放节点
        temp = []

        # 写一个 dfs 方法按 inorder 遍历 BST，将各节点存放入 temp 中
        def dfs(node):
            if not node: return
            dfs(node.left)
            temp.append(node)
            dfs(node.right)

        dfs(root)
        
        # 创建一个 sort 数组，将各节点 value 值按升序排列
        srt = sorted(n.val for n in temp)
        
        # for 循环一一比照节点值和对应 srt 值，进行置换
        # 置换完成后，BST 也就恢复了……
        for i in range(len(srt)):
            temp[i].val = srt[i]

Constraints

• The number of nodes in the tree is in the range [2, 1000].
• -231 <= Node.val <= 231 - 1

测试

• 当就只有 2 个节点时
• 节点数量，各节点 value 值一致时，随意置换节点，选取不同节点做 root
• ……

Big O

• 时间复杂度：O（n）
• 空间复杂度： O（n）

总结

• 本题复习了 BST 的节点 value 值与 inorder 的关联特征
• 还复习了用 dfs 做 inorder 遍历
• 中档题和简单题的区别在于：简单题考查你知不知道 inorder、BST……；中档题在掌握知识的基础上还需要活学活用……🙈