题解 | #二叉搜索树与双向链表#

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def getConversion(self, root):
        if root is not None:
            if root.left is not None:
                lhead,ltail = self.getConversion(root.left) #返回双向链表的头和尾结点
            else:
                lhead = None
                ltail = None
            if root.right is not None:
                rhead,rtail = self.getConversion(root.right) # 返回双向链表的头结点
            else:
                rhead = None 
                rtail = None
            root.left = ltail
            root.right = rhead

            if ltail is not None:
                ltail.right = root
            else:
                lhead = root
            if rhead is not None:
                rhead.left = root
            else:
                rtail = root

            return lhead,rtail
        else:
            return root,root


    def Convert(self , pRootOfTree ):
        # write code here
        # 深度遍历 还是需要用到递归
        if pRootOfTree is None:
            return pRootOfTree
        head,pre = self.getConversion(pRootOfTree.left) #返回双向链表的头和尾结点
        sub,tail = self.getConversion(pRootOfTree.right) # 返回双向链表的头和尾结点

        pRootOfTree.left = pre
        pRootOfTree.right = sub
        if pre is not None:
            pre.right = pRootOfTree
        else:
            head = pRootOfTree
        if sub is not None:
            sub.left = pRootOfTree
        return head