二叉搜素树可用来对n个元素进行排序。试编写一个排序算法，首先将几个元素a[1：n]插人到一个空的二叉搜素树中,然后对树进行中序遍历，并将元素按序放人数组a中。为简单起见，假设a 中的数据互不相同。试编写一个西数，从一棵二叉搜索树中删除最大元素。要求函数的时问复杂性必须是D（1），其中h是二叉搜索树的高度。

排序算法：

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def inorder_traversal(root, res):
    if root:
        inorder_traversal(root.left, res)
        res.append(root.val)
        inorder_traversal(root.right, res)
        
def sort_array(nums):
    root = None
    for num in nums:
        root = insert(root, num)
    res = []
    inorder_traversal(root, res)
    return res

删除最大元素的函数：

def delete_max(root):
    if not root.right:
        return root.left
    root.right = delete_max(root.right)
    return root

函数的时间复杂度为O(h)，其中h是二叉搜索树的高度。