Leetcode 剑指 Offer II 052. 递增顺序搜索树

题目难度: 简单

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给你一棵二叉搜索树，请按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

题目思考

如何降低时间和空间复杂度?

解决方案

思路

根据题目描述, 一个很容易想到的思路就是中序遍历, 然后将遍历到的节点用列表存下来, 最后遍历列表, 并依次将每个节点的右子节点指向列表里的下一个节点, 当然也要把左子节点置为空
不过这样我们就得遍历每个节点两遍, 而且需要额外的列表来存储节点, 有没有更好的方法呢?
回顾二叉搜索树的性质, 其中序遍历的节点本身就是有序的, 所以如果我们保存了前一个节点, 那么在遍历当前节点时, 只需要将前一个节点的右子节点指向它即可, 然后将前一节点更新为当前节点, 以此类推, 这样最终中序遍历完成时, 就得到了题目要求的递增顺序搜索树
当然, 我们在遍历到当前节点时, 也需要将其左子节点置为空, 这里之所以将当前节点而不是前一节点的左子节点置为空, 是因为这样才能保证最终所有节点的左子节点都是空, 否则最后一个节点的左子节点就可能不是空, 会导致出现循环
利用上述做法, 我们就无需引入额外的列表存储, 也不需要再次遍历了
另外在遍历第一个节点时, 由于它没有前一节点, 所以我们可以额外引入一个哨兵节点, 并将最开始的前一节点初始化为哨兵, 这样哨兵的右子节点就是最终形成的树的根, 返回它即可
下面代码中有详细的注释, 方便大家理解

复杂度

时间复杂度 O(N): 每个节点只会被遍历一次
空间复杂度 O(H): 递归调用最多使用 O(H) 栈空间, H 是树的高度

代码

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        # 使用哨兵节点, 作为最开始的前一节点
        dummy = TreeNode()
        pre = dummy

        def inorder(node):
            # 中序遍历
            nonlocal pre
            if not node:
                return
            inorder(node.left)
            # 将当前节点的左子节点置为空, 注意不能将pre的左子节点置为空, 否则会漏掉最后一个节点
            node.left = None
            # 将前一节点的右子节点指向当前节点
            pre.right = node
            # 更新前一节点为当前节点
            pre = node
            inorder(node.right)

        inorder(root)
        return dummy.right