选取中间元素将有序数组转为高度平衡BST：为何该方法有效？

我正在完成一道将有序数组转换为高度平衡二叉搜索树（每个节点的左右子树高度差至多为1）的练习题。
有一种简单的解决方案：选取数组中间元素作为根节点（中间指(0 + 数组长度)整数除法的结果），再分别递归处理剩余数组的左半部分和右半部分，生成左、右子节点。
测试验证该方案可行（文末附有C++示例代码），但我难以证明该方案为何有效。

我尝试用归纳法推理：对于高度K>3的任意节点，假设所有高度k<K的节点满足两个条件：

• 1）是高度平衡的；
• 2）若k−2≥0，则高度k−2的节点的最大可能大小+1 小于 高度k的节点的最小大小。

由于节点最大大小随高度严格递增，条件2意味着若高度差≥2，则大小差≥2。借助归纳假设，不难证明高度K的节点是高度平衡的，但我难以证明针对K的条件2。

以下是包含基准情况的大小表：

最小和最大大小满足以下递推关系：

• 高度K的节点的最小大小 = 1 + 高度K−1的节点的最小大小 + 高度K−2的节点的最小大小 = Fib(n)+n *
• 高度K的节点的最大大小 = 高度K−1的节点的最大大小 ×2 +1 = 2^(n-1) −1

*最后一个等号“可能成立”

Fib(n)+n似乎大于2^(n-1)，但要证明这个复杂的不等式需要涉及斐波那契数列的舍入关系等内容，过程繁琐。

我是否忽略了什么简单的思路？是否存在更简便的方法来证明该解决方案的正确性？

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void deleteTree(TreeNode* root) {
    if (root) {     
        if (root->left) {
            deleteTree(root->left);
        }
        if (root->right) {
            deleteTree(root->right);
        }
        delete root;
    }
}

// 可以把树输出成Graphviz脚本用于可视化；相关代码较复杂，这里省略

// 理论上以下代码应放在单独文件中

#include<vector>
#include<iostream>

#define DEBUG

TreeNode* sortedArrayToBST(std::vector<int>& nums, std::size_t i, std::size_t j) {     
#ifdef DEBUG
    std::cout << "i = " << i << "\tj = " << j << '\n';
#endif // DEBUG
    if (i >= j) {
        return nullptr;
    }
    else {
        std::size_t k{ (i + j) / 2 };
#ifdef DEBUG
        std::cout << "\tk = " << k << '\n';
#endif // DEBUG
        TreeNode* node{ new TreeNode(nums[k]) };
        node->left = sortedArrayToBST(nums, i, k);
        node->right = sortedArrayToBST(nums, k+1, j);
        return node;
    }
}

TreeNode* sortedArrayToBST(std::vector<int>& nums) {
    return sortedArrayToBST(nums, 0, nums.size());
}

int main() {
    std::vector<int> q1{ -4, -3, 0, 1, 2 };
    TreeNode* node{ sortedArrayToBST(q1) };
    deleteTree(node);
}

内容的提问来源于stack exchange，提问作者Argyll