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

最简单的思想，时间复杂度0(n),空间复杂度0(1),先用一个针，把树中的节点串一遍，即中序遍历把输出过程，改成单链表连接。然后遍历一遍链表，修改第二方向的指针，即可得到双链表。

# 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 pRootOfTree == None:
            return pRootOfTree
        self.parent = None
        self.head = None
        self.dfs(pRootOfTree)
        if self.head.right == None:
            return self.head
        else:
            p1 = self.head
            p2 = self.head.right
            while p2!=None:
                p2.left = p1
                p1 = p2
                p2 = p2.right
        return self.head
    
    def dfs(self, pRoot):
        if pRoot == None:
            return
        self.dfs(pRoot.left)
        if self.parent == None:
            self.parent = pRoot
            self.head = pRoot
        else:
            self.parent.right = pRoot
            self.parent = pRoot
        self.dfs(pRoot.right)