Python二叉搜索樹與雙向鏈表轉(zhuǎn)換算法示例
本文實(shí)例講述了Python二叉搜索樹與雙向鏈表轉(zhuǎn)換算法。分享給大家供大家參考，具體如下：
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。
普通的二叉樹也可以轉(zhuǎn)換成雙向鏈表，只不過不是排序的
思路：
1. 與中序遍歷相同
2. 采用遞歸，先鏈接左指針，再鏈接右指針
代碼1，更改doubleLinkedList，最后返回list的第一個(gè)元素：
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指向雙向鏈表中的最后一個(gè)節(jié)點(diǎn)，因此每次操作最后一個(gè)節(jié)點(diǎn)。這里要更改值，因此采用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]
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
樹莓派與PC端在局域網(wǎng)內(nèi)運(yùn)用python實(shí)現(xiàn)即時(shí)通訊
這篇文章主要為大家詳細(xì)介紹了樹莓派與PC端在局域網(wǎng)內(nèi)運(yùn)用python實(shí)現(xiàn)即時(shí)通訊，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-06-06
python實(shí)現(xiàn)單機(jī)五子棋對(duì)戰(zhàn)游戲
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)單機(jī)五子棋對(duì)戰(zhàn)游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-04-04
python pow函數(shù)的底層實(shí)現(xiàn)原理介紹
這篇文章主要介紹了python pow函數(shù)的底層實(shí)現(xiàn)原理介紹，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-03-03
這篇文章主要介紹了PyCharm2019 安裝和配置，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-07-07
本文主要介紹了Selenium+Python自動(dòng)化測試入門，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
如何使用python實(shí)現(xiàn)模擬鼠標(biāo)點(diǎn)擊
這篇文章主要介紹了如何使用python實(shí)現(xiàn)模擬鼠標(biāo)點(diǎn)擊,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
Django基礎(chǔ)知識(shí) web框架的本質(zhì)詳解
這篇文章主要介紹了Django基礎(chǔ)知識(shí) web框架的本質(zhì)詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
Python的文本處理是經(jīng)常碰到的一個(gè)問題，非常重要的，這篇文章主要和大家分享的是3個(gè)Python讀取文本文件內(nèi)容的常用方法，希望對(duì)大家深入學(xué)習(xí)Python有所幫助2023-07-07
常見的在Python中實(shí)現(xiàn)單例模式的三種方法
這篇文章主要介紹了常見的在Python中實(shí)現(xiàn)單例模式的三種方法,單例模式在各個(gè)編程語言的學(xué)習(xí)中都是需要掌握的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-04-04
基于Python和Tkinter實(shí)現(xiàn)高考倒計(jì)時(shí)功能
隨著高考的臨近,每個(gè)考生都在緊鑼密鼓地復(fù)習(xí),這時(shí)候,一款實(shí)用的倒計(jì)時(shí)軟件能有效幫助你規(guī)劃剩余時(shí)間,提醒你不要浪費(fèi)每一分每一秒,今天,我們來聊聊一款基于Python和Tkinter開發(fā)的高考倒計(jì)時(shí)軟件,功能簡單卻極具實(shí)用性,讓你在緊張的備考過程中不再迷失2025-03-03