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

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        # 如果为空直接返回；
        if not pRootOfTree:
            return None
        def dfs(cur):
            # 如果是叶子节点直接返回
            if not cur.left and not cur.right:
                return
            # 如果当前的左节点节点不为空
            if cur.left:
                # 递归左节点
                dfs(cur.left)
                # 将当前节点的左指针指向左链表右节点
                while cur.left.right:
                    cur.left = cur.left.right
                # 将左链表右节点的右指针指向当前节点
                cur.left.right = cur
            # 如果当前的右节点节点不为空
            if cur.right:
                # 递归右节点
                dfs(cur.right)
                # 将当前节点的右指针指向右链表左节点
                while cur.right.left:
                    cur.right = cur.right.left
                # 将右链表左节点的左指针指向当前节点
                cur.right.left = cur
        dfs(pRootOfTree)
        # 将头指针指向头节点
        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left
        return pRootOfTree