題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

創新互聯建站于2013年成立，是專業互聯網技術服務公司，擁有項目做網站、網站設計網站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元鳳慶做網站,已為上家服務,為鳳慶各地企業和個人服務,聯系電話:18980820575

# -*- 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的中序遍歷就是從小到大的，符合有序鏈表的定義，那么可以考慮從中序遍歷著手。

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

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

        return pHeadOfList

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

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

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

        return pLastNodeInList

名稱欄目：劍指offer：二叉搜索樹與雙向鏈表
文章地址：http://m.newbst.com/article42/gscpec.html

成都網站建設公司_創新互聯，為您提供軟件開發、品牌網站制作、App設計、網頁設計公司、企業網站制作、建站公司

廣告

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