我正在做一个练习，将排序数组转换为二叉搜索树，其中树中的每个节点都有其高度最多相差 1 的子节点。
一个简单的解决方案是挑选中间元素作为根。中间为 (0+size) 整数除以 2，然后分别对剩余数组的左半部分、右半部分进行递归调用，生成左子元素、右子元素。
并且可以通过一些测试来检查该解决方案是否有效。 （最后附有 C++ 示例代码。）
但是，我无法证明为什么这个解决方案有效。
为什么？
我尝试归纳推理：对于任何高度K>3的节点，假设所有高度k
由于最大尺寸严格随高度增加，(2) 表示如果高度差 ≥2，则尺寸差 ≥2。
很容易证明任何具有高度 K 的节点都与归纳假设高度平衡。但我在证明 K 的第 (2) 部分时遇到困难。
下面是尺码表，还有基本情况。
| 高度 | 最小尺寸 | 最大尺寸 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 4 | 7 |
| 4 | 7 | 15 |
最小和最大尺寸具有以下递推关系：
高度 K 个节点的最小尺寸 = 1 + 高度 K−1 个节点的最小尺寸 + 高度 K−2 个节点的最小尺寸 = Fib(n)+n *
高度 K 节点的最大尺寸 = K−1 节点的最大尺寸 x 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;
}
}
// one can print the tree to Graphviz script for example for inspection; my code for that has a lot of other things together so I'll skip that
// technically meant to be a different file below
#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);
}
让我们先考虑简单的情况。
根据数组长度 n 将树的叶子的最大深度写为 max(n)，最小值为 min(n)。让我们定义空树的高度 为零，具有一个元素的树的高度为 1，依此类推（这又是 1 比传统的树高定义要好，但它使事情变得更清晰，所以。）
引理： (∀k∈ℕ)(max(2ᵏ - 1) = min(2ᵏ - 1) = k)
基本情况：k = 0给出n = 0，这是空树，并且max(0) = min(0) = 0.
归纳：给定k∈ℕ-{0}。考虑长度为 n = 2ᵏ - 1 的数组。这 算法以一个元素作为中心节点，然后在每个子数组上递归 长度 (2ᵏ - 2) / 2 = 2ᵏ⁻1 - 1。 根据归纳假设， max(2ᵏ⁻1 - 1) = min(2ᵏ⁻1 - 1) = k - 1。所以 *max(2ᵏ - 1) = min(2ᵏ - 1) = k)。
现在考虑不太圆的情况。
定理： (∀nεℕ)(max(n) = ceil(log2(n + 1)) 和 min(n) = Floor(log2(n + 1)))
基本情况：和以前一样。
归纳：给定n∈ℕ-{0}。让 k = 下限(log2(n + 1)).
如果 k = log2(n + 1)，则 n = 2ᵏ - 1，因此根据引理，我们有 max(n) = min(n) = log2(n + 1) = ceil(log2(n + 1)) = Floor(log2(n + 1)) 我们就完成了。
否则， n ≥ 2ᵏ 且 n ≤ 2ᵏ⁺¹(k + 1) - 2 （否则我们可以得到 与 k) 的定义直接矛盾。
对长度为 n 的数组进行操作的算法将取一个元素 长度为 floor((n - 1)/ 2) 和 ceil((n - 1) 的子节点的根和递归 / 2)，我们将其长度分别定义为 l 和 r。
注意 max 和 min 不减，因此 min(l) ≤ min(r) 和 max(l) ≤ 最大（r）。我们只需要检查 min(l) 并且 最大（r）。
l = 下限((n - 1) / 2) ≥ (n - 2) / 2 = n / 2 - 1 所以 min(l) ≥ 楼层(log2(n / 2)), 我们知道 n ≥ 2ᵏ 所以我们有 min(l) ≥ 下限(log2(2ᵏ / 2)) = k - 1.
r = ceil((n - 1) / 2) ≤ n / 2 所以 max(r) ≤ 下限(log2(n / 2 + 1))，并且 我们有 n ≤ 2ᵏ⁺1 - 2 所以 max(r) ≤ 下限(log2((2ᵏ⁺1 - 2)/2 + 1)) = 楼层(log2((2ᵏ⁺1)/2)) = k.
因此我们有 min(n) >= k 和 max(n) <= k + 1,
当然我们知道 min(n) < max(n) 因为仅在平衡情况下 min(n) = max(n) 我们已经排除了上面的情况，所以 min(n) = k 和 max(n) = k + 1。