108. 将有序数组转换为二叉搜索树

【题目】：108. 将有序数组转换为二叉搜索树
二叉搜索树的特征：左 < 根 < 右
所以可以将数组最中间的数作为根节点，依次把根左边的数组和根右边的数组作为左右节点即可。

class Solution {
public:
    TreeNode* help(vector<int> nums, int l, int r) { // [l, r)
        if(l == r) {
            return nullptr;
        }
        int mid = l + (r - l) / 2;
        TreeNode *node = new TreeNode(nums[mid]);
        node->left = help(nums, l, mid); // [l, mid)
        node->right = help(nums, mid + 1, r); // [mid + 1, r)
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return help(nums, 0, nums.size());
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

注意，[l, r)是左闭右开的情况，所以在后边划分区间的时候，也要始终保持左闭右开。