递归取中点构建 BST，为什么能保证高度平衡？

2026-11-04数据阿明

递归选择中点构造出的二叉树一定是高度平衡的。证明需要用到一个事实：这种方法生成的树，其高度由节点数决定。设空树高度为 0、叶节点高度为 1，那么包含 n 个节点的构造结果满足：

n = 0 时，h(n) = 0。
n ≥ 1 时，h(n) = ⌊log₂ n⌋ + 1。

由公式可知，对于用该算法生成的两棵树，如果节点数相同或相差 1，它们的高度最多相差 1。下面用强归纳法同时证明树高公式和高度平衡，避免循环论证。

为什么只看节点数还不够？

对于任意两棵二叉树，节点数接近并不能保证高度接近。例如，两棵树都包含 7 个节点，其中一棵可以是一条高度为 7 的链，另一棵可以是一棵高度为 3 的满二叉树。

证明需要用到完整的递归规则：每次递归都选择中点，而不只是最外层把数组分成大小接近的两部分。

用强归纳法证明

定义函数 g：

g(0) = 0
g(n) = ⌊log₂ n⌋ + 1    （n ≥ 1）

这个函数有两个性质：

g 单调不减。
对任意整数 m ≥ 0，g(m + 1) − g(m) 只能是 0 或 1。

随着节点数逐个增加，g 只在节点数到达 1、2、4、8 等位置时增加 1，其余时候保持不变。

对 n 作强归纳，同时证明：算法生成的树高度为 g(n)，且每个节点都满足高度平衡。

基础情况

n = 0 时返回空树，高度为 0，满足条件。

n = 1 时返回单个节点，高度为 1，左右子树均为空，也满足条件。

归纳假设

设 n ≥ 2，并假设对于所有小于 n 的数组长度，算法都生成高度平衡的树，且树高符合 g 的定义。

分析当前递归

选择中点后，左右子数组的长度分别是：

a = n // 2
b = n - 1 - a

因此，a ≥ b，且 a − b 只能是 0 或 1。

左右子数组的长度都小于 n。根据归纳假设，左右子树内部都满足高度平衡，两棵子树的高度分别为 g(a) 和 g(b)。

由于 a、b 相同或相邻，根据 g 的性质，有：

|g(a) − g(b)| ≤ 1

所以当前根节点也满足高度平衡。左右子树内部的节点已经满足条件，整棵树因此是高度平衡的。

接下来验证当前树的高度。由于 a ≥ b，且 g 单调不减：

h(n) = 1 + max(g(a), g(b))
     = 1 + g(n // 2)

对于 n ≥ 2，有：

⌊log₂(n // 2)⌋ = ⌊log₂ n⌋ − 1

因此：

h(n) = 1 + (⌊log₂(n // 2)⌋ + 1)
     = ⌊log₂ n⌋ + 1
     = g(n)

树高公式和高度平衡性质均已得到验证，归纳完成。

对应到代码

原来的递归实现符合上述证明，只需保持正确的 Python 缩进：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None

        mid = len(nums) // 2
        left = self.sortedArrayToBST(nums[:mid])
        right = self.sortedArrayToBST(nums[mid + 1:])
        return TreeNode(nums[mid], left, right)

这段代码沿用题目环境提供的 List、Optional 和 TreeNode 定义。

例如，n = 8 时，左右子数组分别有 4 个和 3 个元素。按同样的方法递归构造后，两棵子树的高度分别为 3 和 2，高度差为 1。

证明时需要注意什么？

不能仅凭“左右节点数最多相差 1”就得出高度平衡，还需要说明递归构造出的子树高度如何随节点数变化。强归纳法同时证明了这两点。

高度平衡要求每个节点都满足条件。归纳假设保证子树内部的节点满足条件，再验证当前根节点，才能覆盖整棵树。

数组有序用于保证 BST 的有序性；高度平衡的证明只依赖中点划分，与数组中的具体数值无关。如果输入包含重复值，BST 的有序性还需要结合题目对重复键的约定判断。