本文實例講述了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程序設計有所幫助。
新聞熱點
疑難解答
