把二元查找树转变成排序的双向链表 ？

将二元查找树（Binary Search Tree, BST）转换为排序的双向链表可以通过中序遍历（In-order Traversal）实现。中序遍历会按照升序访问BST的所有节点。

以下是一个简单的Python算法，它使用递归来实现中序遍历，并在遍历过程中将节点连接起来形成双向链表：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.prev = None
        self.next = None

def convertBSTtoDLL(root):
    if not root:
        return None

    # 递归地处理左子树
    left_tail = convertBSTtoDLL(root.left)

    # 处理当前节点
    if not left_tail:
        # 当前节点是左子树中最右边的节点
        return root

    # 找到左子树中最右边的节点
    while left_tail.right:
        left_tail = left_tail.right

    # 连接左子树和右子树
    left_tail.right = root
    root.prev = left_tail

    # 递归地处理右子树
    # 右子树中的所有节点将被连接到当前节点
    root.right = convertBSTtoDLL(root.right)
    if root.right:
        root.right.prev = root

    # 返回中序遍历的最后一个节点
    return root.right if root.right else root

# 示例
# 构建一个BST
#      4
#    /   \
#   2     7
#  / \   / \
# 1   3 6   9

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)

# 转换为排序的双向链表
dll_head = convertBSTtoDLL(root)

# 打印双向链表
current = dll_head
while current:
    print(current.val, end=' ')
    current = current.next

这个算法的时间复杂度是O(n)，其中n是BST中的节点数。每个节点只被访问一次。空间复杂度是O(h)，其中h是BST的高度。在最坏的情况下（BST退化为链表），空间复杂度是O(n)。然而，对于平衡的BST，空间复杂度是O(log n)。