二叉搜索树与双向链表

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

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
class Solution:
    def Convert(self, root):
        # write code here
        if not root: return None
        def Convert2(root):
            if not root.left and not root.right: return root, root
            
            l1=r1=l2=r2=None
            if root.left:  l1,r1 = Convert2(root.left)
            if root.right: l2,r2 = Convert2(root.right)
            
            root.left = r1
            if r1: r1.right = root
            
            root.right = l2
            if l2: l2.left = root
            
            if not l1 and not r1: return root, r2
            if not l2 and not r2: return l1, root
            return (l1, r2)
        
        res = Convert2(root)
        return res[0]