Python二叉搜索樹與雙向鏈表轉(zhuǎn)換算法示例

更新時(shí)間：2019年03月02日 12:07:24 作者：hustfc

這篇文章主要介紹了Python二叉搜索樹與雙向鏈表轉(zhuǎn)換算法,涉及Python二叉樹構(gòu)建、遍歷及鏈表構(gòu)造等相關(guā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ì)有所幫助。

您可能感興趣的文章: