用C++讲讲 有序数组转平衡BST 的最佳思路

C++ 里思路和之前讲的一样，核心还是分治：利用数组有序这个性质，每次取当前区间的中间元素作为根，保证左右子树节点数最多相差 1，然后对左右两半区间递归构造。

先给出标准的 TreeNode 定义和实现：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, (int)nums.size() - 1);
    }

private:
    TreeNode* build(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = build(nums, left, mid - 1);
        node->right = build(nums, mid + 1, right);
        return node;
    }
};

几个 C++ 里需要留意的点：

mid 用 left + (right - left) / 2 而不是 (left + right) / 2，是为了避免 left、right 都很大时相加溢出 int，这在 C++ 里是需要显式注意的，不像某些语言有大数保护。

递归参数传的是 vector 的引用（vector<int>&），避免每层递归都拷贝一份数组，这在 C++ 里对性能影响比较明显，尤其数组较大时。

内存管理上，这里用 new 创建节点后不做手动 delete，是因为构造出的树是要返回给调用者持有的，生命周期由调用者负责；如果这是要在函数内部临时用一下就丢弃的场景，才需要考虑用 unique_ptr<TreeNode> 或手动释放，防止内存泄漏。

关于偶数长度区间取左中点还是右中点（left + (right - left) / 2 是取左中点，如果想取右中点用 left + (right - left + 1) / 2），两种写法构造出的树形状不同但都平衡，一般题目不限定具体取哪一个。

复杂度上，时间是 O(n)，因为每个元素恰好被访问一次并创建一个节点；空间上除去输出树本身，额外用的是递归调用栈，深度是 O(log n)，因为每次区间长度减半。

如果数组规模非常大，担心递归栈溢出（C++ 默认栈空间比堆小很多），可以改成迭代版本，用一个显式栈存储 (left, right, 父节点指针, 是左孩子还是右孩子) 这样的三元组/结构体，手动模拟递归过程，把递归深度的限制转移到堆内存上，这在处理超大数据集时是更稳妥的写法，但代码会复杂不少，一般笔试面试场景写递归版本就足够了。