C++如何将有序数组转换为最小高度树-C++-PHP中文网

选中点作为根节点能保证最小高度，因为中点分割使左右子树节点数最均衡，避免某侧多出一层；递归边界为left>right时返回nullptr，且需用new动态分配节点。

c++如何将有序数组转换为最小高度树

为什么选中点作为根节点才能保证最小高度

因为二叉搜索树的高度取决于左右子树的最大深度，而要让整棵树高度最小，必须让左右子树节点数尽可能均衡。对有序数组而言，每次取 mid = (left + right) / 2 对应的元素作根，能天然把剩余元素均分为左右两段——左段构左子树，右段构右子树。如果偏左或偏右取，某侧子树会多出一层，整体高度就上去了。

注意：C++ 中整数除法向零截断，(left + right) / 2 在不溢出前提下是安全的；但更健壮写法是 left + (right - left) / 2，避免 left + right 溢出（尤其当数组极大时）。

递归实现的关键边界与 nullptr 处理

递归终止条件不是 left == right，而是 left > right，此时返回 nullptr。漏掉这个判断会导致访问越界或无限递归。

输入空数组？传入 left = 0, right = -1，直接满足 left > right，返回 nullptr
单元素？left == right，构造一个节点，左右子指针自然为 nullptr
务必用 new TreeNode(nums[mid])，而非栈上临时对象——否则函数返回后节点就被销毁

完整可运行代码片段（含头文件与测试）

#include <vector>
#include <memory><p>struct TreeNode {
int val;
TreeNode <em>left;
TreeNode </em>right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode <em>left, TreeNode </em>right) : val(x), left(left), right(right) {}
};</p>
<p>TreeNode* sortedArrayToBST(const std::vector<int>& nums) {
if (nums.empty()) return nullptr;</int></p>
<pre class="brush:php;toolbar:false;">auto build = [&](auto&& self, int left, int right) -> TreeNode* {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = self(self, left, mid - 1);
    root->right = self(self, mid + 1, right);
    return root;
};
return build(build, 0, nums.size() - 1);

}