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

from re import L
# 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 ):
        if not pRootOfTree:
            return None
        
        nodes = []
        def midSequence(r):
            l = []
            if r.left:
                l.extend(midSequence(r.left))
            l.append(r)
            if r.right:
                l.extend(midSequence(r.right))
            return l
        
        nodes.extend(midSequence(pRootOfTree))

        for i in range(len(nodes)-1):
            nodes[i].right = nodes[i+1]
            nodes[i+1].left = nodes[i]
        
        return nodes[0]