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;

    }

};