我在做 Leetocde 108: 将排序数组转换为二叉搜索树。

输入是一个有序整数数组，目标是返回一个高度平衡的二叉搜索树（BST），也就是说对每个节点，左子树和右子树的深度之差至多为1。

一种自然的递归做法是选取中间元素作为根节点，然后从数组的左半部分递归构建左子树，从右半部分递归构建右子树。下面给出这一思路的实现。

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)

我知道这个算法会返回一个BST，但我很难理解为什么它会得到一棵高度平衡的树。从代码可以看出，nums[:mid]和nums[mid+1:]的大小差距至多为1，但这并不直接说明左、右子树的高度差也至多为1。

我在这里找到了一个相关的帖子 here ，但我并不理解证明。

我希望如果有人能给出这个递归方法的证明。谢谢。

解决方案

如你所提到的，这种归纳证明的方法很适合证明这一性质。我的表述如下：

高度为 ⌈log2(𝑛+1)⌉−1

1.断言

让我们证明对任意 𝑛≥0，所生成二叉树的高度是 ℎ(𝑛)=⌈log2(𝑛+1)⌉−1。我们把高度定义为从根到最远叶子边数。

注：一个更简单的高度表达式是 ⌊log2𝑛⌋，但那样在 𝑛=0时需要单独的情况，此时高度为 -1。所以我更倾向于前面那个表达式。

2.基本情形

当 𝑛=0时，生成的二叉树高度为 -1，因此断言为真。注意，这个情况对应递归算法中的基本情况，即它返回 None。

3.归纳情形

对 𝑛>0的情况，假设对所有节点数少于 𝑛 的生成二叉树，断言成立（这是归纳假设）。

基于这个假设，断言对生成树中的所有真正子树都成立。具体地，算法为根节点创建两棵子树，左子树有 𝑛/2个节点（/ 表示整数除法），右子树有 (𝑛−1)/2个节点。左子树的高度为h(𝑛/2)，右子树的高度为h((𝑛−1)/2)。

整棵树的高度 ℎ(𝑛) 比最高子树的高度多1：

ℎ(𝑛) = Max[h(𝑛/2), h((𝑛−1)/2)] + 1

= h(𝑛/2) + 1

= ⌈log2(𝑛/2+1)⌉ − 1 + 1

= ⌈log2(𝑛/2+1)⌉

= ⌈log2((𝑛+2)/2)⌉

为简化整数除法，我们将 𝑛 区分为偶数和奇数两种情况：

1. 当 𝑛 为偶数时，继续如下：

= ⌈log2(𝑛+2) − log22⌉

= ⌈log2(𝑛+2)⌉ − 1

由于2 的幂在指数大于0时都是偶数，上式在 𝑛 为偶且 𝑛>0时等于：

= ⌈log2(𝑛+1)⌉ − 1 2.当 𝑛 为奇数时，(𝑛+2)/2 = (𝑛+1)/2，因此继续：

= ⌈log2((𝑛+1)/2)⌉

= ⌈log2(𝑛+1) − log22⌉

= ⌈log2(𝑛+1)⌉ − 1

因此在两种情形下得到相同的结果：

ℎ(𝑛) = ⌈log2(𝑛+1)⌉ − 1

这就证明了当输入规模为 𝑛 时，若对更小的输入规模成立，则命题也成立。由此对所有 𝑛≥0均成立。

平衡

该断言对生成树的所有子树（包括树本身）都成立。高度公式表明，任意节点的左、右子树的高度（即h(𝑛/2) 和h((𝑛−1)/2)，当该节点的子树有 𝑛 个节点时）要么相等，要么相差最多1（此时左子树较高）。这恰恰意味着二叉树是平衡的。