劍指offer：二叉搜索樹與雙向鏈表

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

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

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

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

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

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

        return pLastNodeInList