Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
给定一个有序数组，求出它的AVL数（平衡二叉树）。
首先，要知道一些概念。
二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别是二叉排序树。
平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。
那么思路是：
1. 找到“最中间”的位置取一个根结点：为了确保高度差绝对值小于等于 1，我们需要找到最中间的位置取根结点。
2. 以根结点为中心，划分从数组开始到根结点结束的左侧数组（根结点的左子树数据），以及从根结点开始到原数组结束为止的右侧数组（根结点的右子树数据）。
3. 重复第 1 步的操作，在左子树数组中找到了我们认为的“最中间”的位置 ；然后重复第 2 步的操作，将该左子树数组划分成了左右两个数组。
4. 一直这样重复下去，依次构造结点的左右子结点指针指向，直到所有的元素都被取完结束，此时也就构造出来了被转换成功的高度平衡的二叉搜索树了。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0) return NULL;
int mid = nums.size()/2;
TreeNode *root = new TreeNode(nums[mid]);
vector<int> leftnode = vector<int>(nums.begin(), nums.begin()+mid);
vector<int> rightnode = vector<int>(nums.begin()+mid+1, nums.end());
if(mid != 0){
root->left = sortedArrayToBST(leftnode);
}
if(mid != nums.size()-1){
root->right = sortedArrayToBST(rightnode);
}
return root;
}
};
