此为历史版本和 IPFS 入口查阅区,回到作品页
土豆炒青椒
IPFS 指纹 这是什么

作品指纹

刷起来 99 ~ 恢复 BST

土豆炒青椒
·
大家好,我们今天接着来做 leetcode

基本信息

  • 题号: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……;中档题在掌握知识的基础上还需要活学活用……🙈
CC BY-NC-ND 2.0 授权