二叉排序树转为有序双向链表，递归解法

思路在注释里详细描述了。

class Solution:
    def Convert(self, pRootOfTree):
        #递归方法
        root=pRootOfTree
        if not root:
            return
        if not root.left and not root.right:
            return root
        #递归得到已经有序的双向链表的左半部分
        left_dlink_head=self.Convert(root.left)
        cur=left_dlink_head
        #左半部分的双向链表的表尾节点应当作为二叉排序树根节点的前一个节点,则要找到双向链表左半部分的表尾
        #需要沿着左半部分的右子树的路径来找
        #需要注意边界条件:二叉排序树的左子树可能为空,需要排除这种情况
        if left_dlink_head:
            while cur.right:
                cur=cur.right
            #找到了双向链表的左半部分的表尾节点
            #把这个双向链表的左半部分的表尾节点的right指针指向二叉排序树的根节点,把二叉排序树的根节点的left指针指向这个双向链表的左半部分的表尾节点
            #这样就完成了:让双向链表的左半部分和二叉排序树的根节点成为新的有序的双向链表
            cur.right=root
            root.left=cur
        #递归得到已经有序的双向链表的右半部分,得到的是有序的双向链表右半部分的表头,即有序的双向链表右半部分的最小的节点
        right_dlink_head=self.Convert(root.right)
        cur=right_dlink_head
        #要把有序的双向链表右半部分和根节点成为新的有序的双向链表,我们不需要像对有序的双向链表的左半部分那样去处理,因为有序的双向链表的右半部分的表头
        #就是有序的双向链表的右半部分中最小的节点，也是大于二叉排序树根节点的所有节点里最小的那个，直接把这个有序的双向链表的右半部分的表头插入到二叉排序树的根节点之后就行
        #和有序的双向链表左半部分的边界条件一样，有序的双向链表的左半部分可能不存在，需要判断
        if right_dlink_head:
            cur.left=root
            root.right=cur
        #最终返回的整个有序的双向链表的表头，如果在二叉排序树的左子树存在的情况下，就是返回双向链表左半部分的表头，否则二叉排序树的左子树为空，则根节点就是有序的双向链表的表头
        #此时，返回根节点即可，返回有序的双向链表的时候，不需要对二叉排序树右子树可能为空的情况做处理了
        return left_dlink_head if left_dlink_head else root