108. Convert Sorted Array to Binary Search Tree

1. Description

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

2. Example

Example 1

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

3. Constraints

• 1 <= nums.length <= $10^4$
• -$10^4$ <= nums[i] <= $10^4$
• nums is sorted in a strictly increasing order.

4. Solutions

Divide && Conquer

n = nums.size()
Time complexity: O(n)
Space complexity: O(logn)

class Solution {
public:
    TreeNode *sortedArrayToBST(const vector<int> &nums) {
        const int n = nums.size();
        return build_tree(nums, 0, n);
    }

private:
    TreeNode *build_tree(const vector<int> &nums, int left, int right) {
        if (left == right) {
            return nullptr;
        }

        int middle = left + (right - left) / 2;
        auto root = new TreeNode(nums[middle]);
        root->left = build_tree(nums, left, middle);
        root->right = build_tree(nums, middle + 1, right);

        return root;
    }
};