二叉搜索树与双向链表的转换@剑指offer

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

思路分析
二叉搜索树BinarySearchTree的特点是，左节点的值小于根节点的值，右节点的值大于根节点的值，并且左右子树遵循同样的规律。

如图为一棵二叉搜索树，由此可见二叉搜索树的规律是：他的中序遍历是有序的序列。
2-5-6-8-9-10-11， 因此如果要判断一棵树是否为二叉搜索树，只要看他的中序遍历是否刚好是有序的。

本题要将二叉搜索树转换成双向链表，在bst中，每一个节点都有两个指针，分别指向它的左右子节点，在双向链表中，每个节点也有两个指针，分别指向它的前驱和后继，因此，二叉搜索树和双向链表之间的转换是可以实现的。只需要变换指针的方向。

以根节点10为例，转换后它的前驱为8，后继为12，分别为左子树的最大节点和右子树的最小节点.

由于转换后的链表是有序排列的，因此可以考虑对bst进行中序遍历，因为bst的中序遍历返回的列表是有序的，刚好符合有序双向链表的条件。
当遍历到根节点10的时候，可以把bst看作三部分：值为10的节点，根节点为6的左子树，根节点为14的右子树。在转换双向链表的时候，我们要做的是把根节点10和左子树的最右节点（也是左子树的最大值）连起来，并且把根节点10和右子树的最左节点（也是右子树的最小值）连起来。
在中序遍历的时候，当遍历完左子树时，链表最后一个节点值为8，然后连接8与10，此时链表最后一个节点值为10，接着遍历转换右子树，并且把右子树的最小节点个根节点10连接，由此可见，遍历和转换的过程是一样的，可以采用递归的思想。

代码实现

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

class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree

        # 转换左子树, 采用递归的思想
        self.Convert(pRootOfTree.left)
        left = pRootOfTree.left

        # 根节点连接左子树的最大节点
        if left:
            while left.right:  # 通过循环，找到左子树的最大节点
                left = left.right  # 左子树的最大节点，为转换后root链表的左节点
            pRootOfTree.left, left.right = left, pRootOfTree

        # 转换右子树， 采用递归的思想
        self.Convert(pRootOfTree.right)
        right = pRootOfTree.right

        # 根节点连接右子树的最小节点
        if right:
            while right.left:  # 通过循环，找到右子树的最小节点
                right = right.left
            pRootOfTree.right, right.left = right, pRootOfTree  # 右子树的最小节点，即为转换后根节点的右节点

        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left
        return pRootOfTree