Python实现二叉搜索树转排序双向链表算法解析

Hazel

发布时间：2026-10-13| 6人浏览过

原创

本文详解Python中将二叉搜索树转换为排序双向链表的算法。通过中序遍历思路，提供两种递归实现方案：一种利用列表存储节点并返回首元素，另一种通过引用传递最后一个节点指针。代码严格遵循原地修改指针的要求，不创建新节点，适合数据结构学习与面试准备。

算法概述与题目要求

本文展示了一种使用Python将二叉搜索树转换为排序双向链表的算法实现，旨在为读者提供清晰的参考案例。

题目描述

给定一棵二叉搜索树，需要将其转换成一个排序的双向链表。关键约束条件是不能创建任何新的节点，仅允许调整树中现有节点的指针指向。

需要注意的是，普通的二叉树同样可以转换为双向链表，但转换后的结果不具备排序特性。

核心解题思路

解题思路：

1. 转换过程与二叉树的中序遍历顺序一致。

2. 采用递归策略，先处理左子树以链接左指针，再处理右子树以链接右指针。

方案一：基于列表返回头节点

代码方案1：通过修改doubleLinkedList列表，最终返回该列表的第一个元素作为链表头：


class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def lastElem(self, list):
    if len(list) == 0:
      return None
    else: return list[len(list) - 1]
  def ConvertCore(self, pRoot, doubleLinkedList):
    if pRoot:
      if pRoot.left:
        self.ConvertCore(pRoot.left, doubleLinkedList)
      pRoot.left = self.lastElem(doubleLinkedList)
      if self.lastElem(doubleLinkedList):
        self.lastElem(doubleLinkedList).right = pRoot
      doubleLinkedList.append(pRoot)
      if pRoot.right:
        self.ConvertCore(pRoot.right, doubleLinkedList)
  def Convert(self, pRootOfTree):
    if pRootOfTree == None:
      return None
    doubleLinkedList = []
    self.ConvertCore(pRootOfTree, doubleLinkedList)
    return doubleLinkedList[0]

方案二：基于引用传递尾节点

代码方案2：使用lastListNode指向双向链表中的最后一个节点，每次操作均针对该节点。由于需要修改列表内部值，此处采用列表形式传递引用。


class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def ConvertCore(self, pRoot, lastListNode):
    if pRoot:
      if pRoot.left:
        self.ConvertCore(pRoot.left, lastListNode)
      pRoot.left = lastListNode[0]
      if lastListNode[0]:
        lastListNode[0].right = pRoot
      lastListNode[0] = pRoot
      if pRoot.right:
        self.ConvertCore(pRoot.right, lastListNode)
  def Convert(self, pRootOfTree):
    # write code here
    if pRootOfTree == None:
      return None
    lastListNode = [None]
    self.ConvertCore(pRootOfTree, lastListNode)
    while lastListNode[0].left:
      lastListNode[0] = lastListNode[0].left
    return lastListNode[0]

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述的算法解析对大家的Python程序设计有所帮助。