题目难度: 中等
原题链接
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号算法精选里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
示例 1：
- 输入：root = [4,2,5,1,3]
- 输出：[1,2,3,4,5]
- 解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。
示例 2：
- 输入：root = [2,1,3]
- 输出：[1,2,3]
示例 3：
- 输入：root = []
- 输出：[]
- 解释：输入是空树，所以输出也是空链表。
示例 4：
- 输入：root = [1]
- 输出：[1]
提示：
- -1000 <= Node.val <= 1000
- Node.left.val < Node.val < Node.right.val
- Node.val 的所有值都是独一无二的
- 0 <= Number of Nodes <= 2000
题目思考
- 如何确定当前节点在链表中的左右节点?
解决方案
方案 1
思路
- 根据题目描述, 一个比较容易想到的思路是分治法, 就是先将左右子树转换成双向链表, 然后再调节当前根节点的指向
- 双向链表需要知道其头和尾, 所以递归的返回值就是转换后的链表头和尾, 这样根节点左边就指向左子树对应链表的尾 ltail, 右边就指向右子树对应链表的头 rhead, 然后返回左边的头 lhead 和右边的尾 rtail, 自然就是当前的树转换后的链表头和尾了
- 注意如果当前根节点某一个子树不存在, 比如根节点只有左子树, 那么根节点右指针就不需要额外指向了, 且根节点就是对应的双向链表的尾. 而如果左右子树都不存在的话, 根节点本身就是对应的双向链表的头和尾. 这里可以将左右子树的头尾都初始化为 root 来实现 (具体参考下面的代码部分)
- 而递归出口自然就是节点为空的情况, 此时对应的链表头和尾都是空
- 这样递归调用, 最后返回的就是整个树转换成的链表的头和尾, 又因为题目要求是循环链表, 所以最后只需要把头尾相连即可
- 下面的代码对关键步骤都有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N)- 每个节点只需要遍历一次
- 空间复杂度
O(N)- 递归栈的空间消耗
代码
classSolution:deftreeToDoublyList(self,root:'Node')->'Node':ifnotroot:returnNonedefgetDoublyList(root):ifnotroot:# 空节点对应的链表头尾也是空return(root,root)# 初始化左右子树对应链表的头和尾lhead,ltail,rhead,rtail=root,root,root,rootifroot.left:# 左子树存在时, 需要将根节点与左子树链表结尾相连lhead,ltail=getDoublyList(root.left)root.left=ltail ltail.right=rootifroot.right:# 右子树存在时, 需要将根节点与右子树链表开头相连rhead,rtail=getDoublyList(root.right)root.right=rhead rhead.left=root# 最后左链表开头和右链表结尾就是当前树转换的链表的头和尾return(lhead,rtail)# 将整个树转换的链表的头和尾相连, 形成循环链表head,tail=getDoublyList(root)head.left=tail tail.right=headreturnhead方案 2
思路
- 这次我们从另外一个角度分析这个问题
- 二叉搜索树的性质是中序遍历有序, 而最终形成的双向链表也是排好序的
- 所以我们可以直接利用中序遍历, 只需要额外存储一个 pre 节点, 然后遍历到当前节点时, 就将其和 pre 节点相连即可
- 另外遍历过程中要找到转换的链表的头和尾, 最后也要把它们也连起来从而形成循环链表
- 下面的代码对关键步骤都有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N)- 每个节点只需要遍历一次
- 空间复杂度
O(N)- 递归栈的空间消耗
代码
classSolution:deftreeToDoublyList(self,root:'Node')->'Node':ifnotroot:returnNoneself.pre=Nonedefinorder(node):ifnotnode:returninorder(node.left)ifnotself.pre:# 说明当前遍历到第一个节点, 也是最小的节点, 就是链表头self.head=nodeelse:# 将pre和node连起来self.pre.right=node node.left=self.pre# 更新pre为当前nodeself.pre=node inorder(node.right)inorder(root)# 注意遍历结束的时候的pre就是最后一个节点, 即链表尾, 需要和之前保存的链表头连起来, 形成循环链表self.head.left,self.pre.right=self.pre,self.headreturnself.head大家可以在下面这些地方找到我~😊
我的 GitHub
我的 Leetcode
我的 CSDN
我的知乎专栏
我的头条号
我的牛客网博客
我的公众号: 算法精选, 欢迎大家扫码关注~😊
