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

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    # 创建两个指针，一个指向头结点，最左边的节点
    # 另一个指向前一个节点（中序就是指向更小的那个节点）
    pre = None
    head = None
    def Convert(self , pRootOfTree ):
        # write code here
        # 核心是中序遍历二叉搜索树，在中序的地方进行操作
        # 递归退出条件
        if pRootOfTree == None:
            return None
        self.Convert(pRootOfTree.left)
        # 到第一个节点要初始化一下
        if not self.pre:
            self.pre = pRootOfTree
            self.head = pRootOfTree
        else:
            # 否则开始连接成一个链表
            # pre 指向前一个节点， pRootOfTree 指向当前节点，注意pRootOfTree不需要加self，因为这是函数自己的东西
            self.pre.right = pRootOfTree
            pRootOfTree.left = self.pre
            # 记得更新pre位置
            self.pre = pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.head

具体做法：

• step 1：创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一节点（pre)。
• step 2：首先递归到最左，初始化head与pre。
• step 3：然后处理中间根节点，依次连接pre与当前节点，连接后更新pre为当前节点。
• step 4：最后递归进入右子树，继续处理。
• step 5：递归出口即是节点为空则返回。