本文共 1549 字，大约阅读时间需要 5 分钟。

为了构造平衡二叉搜索树，我们可以使用中序遍历生成有序数组，然后基于二分法构造平衡树。以下是详细的步骤和代码实现：

步骤说明

代码实现

class TreeNode:    def __init__(self, val):        self.val = val        self.left = None        self.right = Nonedef get_values(node, list_values):    if node is None:        return    get_values(node.left, list_values)    list_values.append(node.val)    get_values(node.right, list_values)def build_balanced_tree(values):    def create_tree(left, right):        if left > right:            return None        mid = (left + right) // 2        current_val = values[mid]        node = TreeNode(current_val)        node.left = create_tree(left, mid - 1)        node.right = create_tree(mid + 1, right)        return node    return create_tree(0, len(values) - 1)def balance_binary_search_tree(root):    if not root:        return None    values = []    get_values(root, values)    return build_balanced_tree(values)# 示例使用root = TreeNode(1)root.right = TreeNode(2)root.right.right = TreeNode(3)root.right.right.right = TreeNode(4)balanced_tree = balance_binary_search_tree(root)# 转换为字符串以便查看print(str(balanced_tree))

代码解释

这种方法确保构造的平衡树满足题目要求，时间复杂度为O(n)，空间复杂度为O(n)。