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

class Solution {
public:
    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;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;
        return helper(nums, 0, nums.size() - 1);
    }
};