难度简单1251收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
递归
这道题使用迭代法实现起来比较复杂，所以这里只将递归法！
这道题要求我们将元素转化为 BST(平衡二叉搜索树)，又称为 AVL树，如果我们自己去实现这个插入的功能，其实需要涉及子树的旋转等操作，比较复杂，但是由于这道题给我们的条件是有序序列，并且是递增的，而二叉搜索树最重要的特性就是其中序遍历的有序性，所以我们利用这两个条件，可以直接构造出对应的 BST 而不用去顾及旋转等操作！
我们每次去取区间内中间的那个元素值去构造节点，为什么❓❓❓因为我们在构建的同时要保证它是平衡的，所以给这个节点附上同样高度的左右子树是很关键的，所以取最中间的元素进行构造，然后再递归到其左区间和右区间继续去构建左右子树，并且链接起来。这样子就能很大程度上保证我们的二叉搜索树是平衡的！
那么要是遇到区间的元素个数是偶数的怎么办❓❓❓这个不用放心，我们取中间这两个元素中的哪一个都行，只不过它们构建出来的形态不一样，但是都会保持平衡的，这也就是这道题说可能构建会有不同情况的原因！
class Solution {
public:
TreeNode* travel(vector<int>& nums, int left, int right)
{
if(left > right)
return nullptr;
// 取每个区间内的中间的值进行构造
int mid = left + (right - left)/2;
TreeNode* newnode = new TreeNode(nums[mid]);
// 继续递归左右子树
newnode->left = travel(nums, left, mid - 1);
newnode->right = travel(nums, mid + 1, right);
return newnode;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return travel(nums, 0, nums.size() - 1);
}
};