题目
简单
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡
二叉搜索树。
示例 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] <= 104-
nums按 严格递增 顺序排列
面试中遇到过这道题?
1/5
是
否
通过次数
471.9K
提交次数
601.7K
通过率
78.4%
思路
平衡二叉搜索树有两个要求
1、每个节点左右子树的高度差不能超过1
2、每个节点的大于所有左子树结点，小于所有右子树结点。
要满足第一个条件的话，我们可以递归建树，每次将中间的值作为根节点，然后递归调用左右两部分。
要满足第二个条件，只需将root->left指向左边部分递归的结果，root->right指向右边部分递归的结果即可。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *creat(int lo,int hi,vector<int>& nums)
{
if(lo>hi) return NULL;
int mid=(lo+hi)/2;
TreeNode *root=new TreeNode;
root->val=nums[mid];
root->left=creat(lo,mid-1,nums);
root->right=creat(mid+1,hi,nums);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int lo=0,hi=nums.size()-1;
TreeNode *root=creat(lo,hi,nums);
return root;
}
};