Python中链表的二叉搜索树转换为排序链表操作

2023-04-11 00:00:00 排序 转换为 链表

实现二叉搜索树转换为排序链表的操作需要分以下几个步骤：

  1. 中序遍历二叉搜索树，记录遍历的节点值
  2. 根据遍历的节点值构建单向链表
  3. 返回单向链表的头节点

下面是代码演示：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def __init__(self):
        self.cur = None  # 用于记录当前遍历到的节点

    def bstToSortedList(self, root: TreeNode) -> ListNode:
        if not root:
            return None

        # 构建左子树的单向链表
        left_head = self.bstToSortedList(root.left)

        # 构建当前节点的单向链表
        cur_node = ListNode(root.val)
        if self.cur:  # 如果cur不为None，则将cur_node挂接到cur的next节点上
            self.cur.next = cur_node
        self.cur = cur_node  # 更新cur为当前节点

        # 构建右子树的单向链表
        right_head = self.bstToSortedList(root.right)

        # 将左子树链表、当前节点链表和右子树链表拼接在一起
        if left_head:
            cur_node.next = left_head
        if right_head:
            self.cur.next = right_head

        # 返回单向链表的头节点
        if left_head:
            return left_head
        else:
            return cur_node

接下来，我们使用一个例子来演示这个操作的使用。

例如，我们有一棵二叉搜索树如下所示：

      5
    /   \
   3     7
  / \   / \
 2   4 6   8

我们需要将它转换为一个排序的单向链表，那么我们可以这样调用函数：

root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, TreeNode(6), TreeNode(8)))
solution = Solution()
head = solution.bstToSortedList(root)

最终得到的单向链表的头节点就是 head 了。我们可以遍历这个链表来查看它是否按照顺序排列：

while head:
    print(head.val)
    head = head.next

# 输出如下：
# 2
# 3
# 4
# 5
# 6
# 7
# 8

相关文章