題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。

我們提供的服務有：成都網(wǎng)站建設、網(wǎng)站制作、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、鄂溫克ssl等。為成百上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術(shù)的鄂溫克網(wǎng)站制作公司

# -*- coding: utf-8 -*-
# @Time         : 2019-07-07 11:03
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : BST2LinkedList.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """
    由于二叉搜索樹BST的中序遍歷就是從小到大的，符合有序鏈表的定義，那么可以考慮從中序遍歷著手。

    如果按照中序遍歷，假設當前轉(zhuǎn)換到了根節(jié)點，那么左子樹已經(jīng)轉(zhuǎn)換完成，即左子樹中的大節(jié)點應該是當
    前鏈表中的末尾節(jié)點，因此根節(jié)點的左指針應該指向該末尾節(jié)點，同時該末尾節(jié)點的右指針應該指向根節(jié)點。
    當把左子樹和根節(jié)點轉(zhuǎn)換完成之后，用同樣的辦法轉(zhuǎn)換右子樹。

    也就是利用遞歸方法，先轉(zhuǎn)換左子樹然后根節(jié)點最后右子樹。**關(guān)鍵在于要保存當前鏈表中的末尾節(jié)點**
    """
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        pLastNodeInList = self.convertNode(pRootOfTree, None)
        # 需要返回鏈表的頭節(jié)點
        pHeadOfList = pLastNodeInList
        while pHeadOfList and pHeadOfList.left:
            pHeadOfList = pHeadOfList.left

        return pHeadOfList

    def convertNode(self, pNode, pLastNodeInList):
        if not pNode:
            return None
        pCurrent = pNode
        # 先轉(zhuǎn)換左子樹
        if pCurrent.left:
            pLastNodeInList = self.convertNode(pCurrent.left, pLastNodeInList)

        # 然后將當前節(jié)點和當前鏈表的末尾節(jié)點鏈接起來
        pCurrent.left = pLastNodeInList
        # 這里需要判斷當前節(jié)點是不是鏈表的頭節(jié)點，如果是，那么pLastNodeInList是None
        if pLastNodeInList:
            pLastNodeInList.right = pCurrent

        # 在鏈接過后，當前節(jié)點就是鏈表的末尾節(jié)點
        pLastNodeInList = pCurrent
        # 然后對右子樹進行轉(zhuǎn)換
        if pCurrent.right:
            pLastNodeInList = self.convertNode(pCurrent.right, pLastNodeInList)

        return pLastNodeInList

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網(wǎng)頁標題：劍指offer：二叉搜索樹與雙向鏈表-創(chuàng)新互聯(lián)
瀏覽路徑：http://www.chinadenli.net/article18/disigp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、云服務器、手機網(wǎng)站建設、搜索引擎優(yōu)化、營銷型網(wǎng)站建設、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)