题目链接：108. 将有序数组转换为二叉搜索树
方法：递归建树
解题思路
每次选取中间的元素作为根节点，递归创建左右子树，就可以保证左右子树的高度差绝对值不超过1
代码
/**
* 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* sortedArrayToBST(vector<int>& nums) {
function<TreeNode*(int, int)> buildAVLTree = [&](int l, int r) -> TreeNode* {
int mid = l + r >> 1;
return l > r ? nullptr : new TreeNode(nums[mid], buildAVLTree(l, mid - 1), buildAVLTree(mid + 1, r));
};
return buildAVLTree(0, nums.size() - 1);
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(logn)\)。