LeetCode 108. 将有序数组转换为二叉搜索树
📌 题目描述
题目级别：简单
给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。
高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
- 示例 1:
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5](答案不唯一，平衡即可)
💡 破题思路：分治与二分法
这道题的核心在于：如何保证“高度平衡”？
因为数组已经是升序排列的，如果我们想让左右子树的节点数量尽可能接近（从而保证高度平衡），最简单的方法就是：
- 取中点：将数组中间的元素作为当前子树的根节点。
- 划分子问题：
- 中点左侧的所有元素，递归地构建成左子树。
- 中点右侧的所有元素，递归地构建成右子树。
- 递归终止：当区间左边界大于右边界时，说明这一侧已经没有元素了，返回空。
这种思路本质上就是二分查找的变种，由于我们总是从中间劈开，左右两边的节点数差值最多为 1，天然满足高度平衡的定义。
💻 C++ 代码实现 (修复引用性能版)
classSolution{public:TreeNode*sortedArrayToBST(vector<int>&nums){// 传入左右边界 [0, n-1]returndfs(nums,0,nums.size()-1);}// 💡 重点：vector<int>& nums 必须加引用，避免每一层递归都拷贝整个数组导致 TLE/MLETreeNode*dfs(vector<int>&nums,intl,intr){// 递归终止条件：区间无效if(l>r)returnnullptr;// 选择中间位置的数字作为根节点// 使用 l + (r - l) / 2 防止 (l + r) 溢出intmid=l+(r-l)/2;TreeNode*root=newTreeNode(nums[mid]);// 递归构建左子树，区间变为 [l, mid - 1]root->left=dfs(nums,l,mid-1);// 递归构建右子树，区间变为 [mid + 1, r]root->right=dfs(nums,mid+1,r);returnroot;}};
