Problem:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
复习一下BST的基本性质：简而言之，对于BST中任意结点x，若其有左右结点 l 或 r ，需满足 l.key ≤ x.key ≤ r.key
BST的性能（基本操作耗时）与树高成正比，可改进为较为高效的平衡二叉树，即保持整棵树左右均匀，任意左右子树高度差不大于1
如题将有序数组转化为二叉平衡树，可将数组从中间分成左右两部分，在分别对中间根节点赋值，左子树和右子树的确定用递归方法
Code:
//in C language /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode *createTree(int left,int right, int nums[]){
if(right-left<)
return NULL;
//if负责终止递归
int mid=(left+right)/;
struct TreeNode *root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val=nums[mid];
root->left=createTree(left,mid-,nums);
root->right=createTree(mid+,right,nums); return root;
} struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
return createTree(, numsSize-, nums);
}
ps:似乎是谷哥哥家的题目～加油！