Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

解析

二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree. BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。
由于题目要求是平衡二叉查找树，因此，我们需要将数组分为两半，分别作为左右子数来保持平衡，用递归的方法很容易实现。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* convert(int* nums,int numsSize,int left,int right)
{
    if(left==right)
    {
        struct TreeNode *newTreeNode=(struct TreeNode *)malloc(sizeof(struct TreeNode ));
        newTreeNode->val=nums[left];
        newTreeNode->left=NULL;
        newTreeNode->right=NULL;
        return newTreeNode;
    }
    if(left<right)
    {
        struct TreeNode *rootNode=(struct TreeNode *)malloc(sizeof(struct TreeNode ));
        rootNode->val=nums[(left+right)/2];
        rootNode->left=convert(nums,numsSize,left,(left+right)/2-1);
        rootNode->right=convert(nums,numsSize,(left+right)/2+1,right);
        return rootNode;
    }
    return NULL;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    if(numsSize==0)return NULL;
    else
        return convert(nums,numsSize,0,numsSize-1);
}