剑指offer：二叉搜索树与双向链表-创新互联
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
# -*- 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另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：剑指offer：二叉搜索树与双向链表-创新互联
标题路径：http://6mz.cn/article/disigp.html