题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

# -*- 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/SysuJayceclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass 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