溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python二叉搜索樹與雙向鏈表轉換算法。分享給大家供大家參考，具體如下：
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。
普通的二叉樹也可以轉換成雙向鏈表，只不過不是排序的
思路：
1. 與中序遍歷相同
2. 采用遞歸，先鏈接左指針，再鏈接右指針
代碼1，更改doubleLinkedList，最后返回list的第一個元素：
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指向雙向鏈表中的最后一個節點，因此每次操作最后一個節點。這里要更改值，因此采用list的形式。
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程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
