题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
- 二叉树数据结构 TreeNode 可用来表示单向链表（其中 left 置空，right 为下一个链表节点）。
- 实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质。
- 转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
- 返回转换后的单向链表的头节点。
- 注意：本题相对原题稍作改动
示例：
- 输入： [4,2,5,1,3,null,6,0]
- 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：
- 节点数量不会超过 100000。
题目思考
- 如何利用二叉搜索树的性质?
- 如何做到在原有树上直接修改?
解决方案
思路
- 看到二叉搜索树, 很容易想到其中序遍历是有序的, 我们可以利用这一性质, 开始中序遍历:
- 头一个遍历的节点作为单向链表的头
- 将其左子节点置空, 右子节点指向下一个遍历的点
- 持续上述过程, 直到遍历到最后一个节点作为链表尾
- 这样就成功转换成了单向链表, 且仍满足二叉搜索树的性质 (只有右子节点, 且比自身大)
- 要想直接在原有树上修改, 我们可以额外维护哨兵和 pre 节点
- 开始时将 pre 置为哨兵, 之后每遍历到一个节点, 就将 pre 右子节点置为当前节点, 然后将当前节点作为新的 pre 即可
- 另外特别注意需要将当前节点的左子节点置空, 否则就多出了额外不属于最终链表的部分
- 下面的代码中对每个步骤都有注释, 方便大家理解
复杂度
- 时间复杂度
O(N): 只需要遍历树一遍 - 空间复杂度
O(H): H 是树的高度, 也是递归栈的空间消耗 (改用 Morris 遍历可使得空间变成 O(1), 感兴趣的小伙伴可以参考之前这篇文章剑指 Offer 54. 二叉搜索树的第 k 大节点 - leetcode 剑指 offer 系列)
代码
class Solution:
def convertBiNode(self, root: TreeNode) -> TreeNode:
# 中序遍历+哨兵+pre
# 全局变量存储当前节点, 需要一个哨兵节点
# 每次中序遍历到node节点时, 将全局节点的右子节点设为该节点
# 然后将node的左子节点设为空, 将全局节点变为node
dummy = TreeNode(0)
pre = dummy
def inorder(node):
nonlocal pre
if not node:
return
inorder(node.left)
# 前一节点的右子节点指向当前节点
pre.right = node
# 更新前一节点为当前节点
pre = node
# 注意当前节点断开与左子节点的连接
node.left = None
inorder(node.right)
inorder(root)
return dummy.right
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号