程序员面试金典 - 面试题 17.12. BiNode

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

• 二叉树数据结构 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。

题目思考

1. 如何利用二叉搜索树的性质?
2. 如何做到在原有树上直接修改?

解决方案

思路

• 看到二叉搜索树, 很容易想到其中序遍历是有序的, 我们可以利用这一性质, 开始中序遍历:
  • 头一个遍历的节点作为单向链表的头
  • 将其左子节点置空, 右子节点指向下一个遍历的点
  • 持续上述过程, 直到遍历到最后一个节点作为链表尾
• 这样就成功转换成了单向链表, 且仍满足二叉搜索树的性质 (只有右子节点, 且比自身大)
• 要想直接在原有树上修改, 我们可以额外维护哨兵和 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊