/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size());
    }
    
    typedef vector<int>::iterator Iterator;
    TreeNode* sortedArrayToBST(vector<int> &nums, int lt, int rt)
    {
        if(lt >= rt)
            return nullptr;
            
        int mid = (lt + rt) / 2;
        TreeNode *ret = new TreeNode(nums[mid]);
        ret->left = sortedArrayToBST(nums, lt, mid);
        ret->right = sortedArrayToBST(nums, mid + 1, rt);
        
        return ret;
    }
};