简述二叉搜索树转为有序双向链表（中序遍历） ？

将二叉搜索树转换为有序双向链表（中序遍历）的过程主要涉及到中序遍历和链表节点的构建。二叉搜索树（BST）的中序遍历结果是一个有序序列，因此我们可以利用这个特性来创建一个有序双向链表。

下面是一个基本的步骤描述：

1. 定义链表节点：首先，你需要定义一个链表节点，该节点包含数据，指向前一个节点的指针和指向后一个节点的指针。

class ListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

2. 中序遍历二叉搜索树：然后，你需要进行中序遍历（左-根-右）以获取有序序列。在遍历过程中，你需要跟踪上一个访问的节点，以便在创建链表时正确设置prev指针。

def inorder_traversal(root):
    if not root:
        return None
    
    # 先递归遍历左子树
    prev = inorder_traversal(root.left)
    
    # 如果左子树遍历结束，prev将是最后一个访问的节点
    if prev:
        prev.next = root
        root.prev = prev
    
    # 递归遍历右子树，并将当前节点作为上一个节点返回
    return inorder_traversal(root.right)

3. 初始化并调用中序遍历：最后，你需要初始化二叉搜索树的根节点，并调用中序遍历函数。这将返回一个指向有序双向链表第一个节点的指针。

def convertBSTtoList(root):
    # 初始化并调用中序遍历
    head = inorder_traversal(root)
    
    # 由于链表是双向的，我们需要设置最后一个节点的next指针为None
    if head:
        while head.next:
            head = head.next
        head.next = None
    
    return head

这个过程的时间复杂度是O(n)，其中n是二叉搜索树中的节点数，因为我们需要访问每个节点一次。空间复杂度也是O(n)，在最坏的情况下，即树完全不平衡时，递归栈的深度可能达到n。然而，由于二叉搜索树的特性，这种情况在实际应用中很少见，因此空间复杂度通常被认为是O(log n)，其中log n是树的高度。