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