Convert Sorted Array to Binary Search Tree [C++]
IntuitionThe problem requires constructing a height-balanced binary search tree (BST) from a sorted array. A BST is height-balanced if the depth of the two subt
### Intuition
The problem requires constructing a height-balanced binary search tree (BST) from a sorted array. A BST is height-balanced if the depth of the two subtrees of every node differs by at most 1. To achieve this, the middle element of the array can act as the root, with the left and right halves recursively forming the left and right subtrees.

---

### Approach
1. Use a recursive helper function that takes the range of indices (`left` and `right`) as parameters.
2. Find the middle index of the current range. This middle element becomes the root of the current subtree.
3. Recursively:
   - Assign the left half of the range (`left` to `mid - 1`) to the left child.
   - Assign the right half of the range (`mid + 1` to `right`) to the right child.
4. Base case: If `left > right`, return `nullptr`.

This approach ensures that the BST is height-balanced as the middle element is always selected as the root for each range.

---

### Complexity
- **Time Complexity**: 
  - $$O(n)$$, where $$n$$ is the size of the array.
  - Each element of the array is processed exactly once during the recursion.
  
- **Space Complexity**: 
  - $$O(\log n)$$ for the recursion stack in a balanced BST, where $$\log n$$ is the height of the tree.

---

### Code
```cpp
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};
```
['C++']