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

解析

二叉排序樹又叫二叉查找樹，英文名稱是：Binary Sort Tree. BST的定義就不詳細(xì)說了，我用一句話概括：左 < 中 < 右。 根據(jù)這個原理，我們可以推斷：BST的中序遍歷必定是嚴(yán)格遞增的。
由于題目要求是平衡二叉查找樹，因此，我們需要將數(shù)組分為兩半，分別作為左右子數(shù)來保持平衡，用遞歸的方法很容易實(shí)現(xiàn)。

/**
 * 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);
}