本文實例講述了Python二叉搜索樹與雙向鏈表轉換算法。分享給大家供大家參考，具體如下：

題目描述

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

普通的二叉樹也可以轉換成雙向鏈表，只不過不是排序的

思路：

1. 與中序遍歷相同

2. 采用遞歸，先鏈接左指針，再鏈接右指針

代碼1，更改doubleLinkedList，最后返回list的第一個元素：

class TreeNode:  def __init__(self, x):    self.val = x    self.left = None    self.right = Noneclass 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指向雙向鏈表中的最后一個節點，因此每次操作最后一個節點。這里要更改值，因此采用list的形式。

class TreeNode:  def __init__(self, x):    self.val = x    self.left = None    self.right = Noneclass 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程序設計有所幫助。