给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。
注意事项
There may exist multiple valid solutions, return any of them.
您在真实的面试中是否遇到过这个题？
Yes
样例
给出数组 [1,2,3,4,5,6,7], 返回
4思路:相当于给出中序遍历的结果，然后将其转换成二叉树。
/ \
2 6
/ \ / \
1 3 5 7
直接采用中间值来作为二叉树的根节点；
将原数组分成左右均等或者相差一个数的两个新数组；
然后递归的对这两个新数组进行相同的处理，这样对于每一个根节点，其左右子树的高度相差绝对值不会超过1，
也就是满足了二叉平衡树的要求了
其实思路很容易想到，但在实现的时候，对于折半后，每次递归边界问题犯了糊涂，绕进去了；
下面的代码，思路就很清晰，学习！
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param A: A sorted (increasing order) array
* @return: A tree node
*/
/* 思路:相当于给出中序遍历的结果，然后将其转换成二叉树 直接采用中间值来作为二叉树的根节点；
将原数组分成左右均等或者相差一个数的两个新数组；
然后递归的对这两个新数组进行相同的处理，这样对于每一个根节点，其左右子树的高度相差绝对值不会超过1，
也就是满足了二叉平衡树的要求了 其实思路很容易想到，但在实现的时候，对于折半后，每次递归边界问题犯了糊涂，绕进去了；
下面的代码，思路就很清晰，学习！ */ TreeNode *sortedArrayToBSTCore(vector<int> &A, int start, int end){
if (start > end){
return NULL;
}
int mid = (start + end) / 2;
TreeNode *head = new TreeNode(A[mid]);//直接初始化了；
head->left = sortedArrayToBSTCore(A, start, mid - 1);
head->right = sortedArrayToBSTCore(A, mid + 1, end);
return head;
} TreeNode *sortedArrayToBST(vector<int> &A) {
// write your code here
if(A.size()==0){
return NULL;
} int start = 0;
int end = A.size() - 1;
int mid = (start + end) / 2;
TreeNode *Head = new TreeNode(A[mid]);
Head->left = sortedArrayToBSTCore(A, start, mid - 1);
Head->right = sortedArrayToBSTCore(A, mid + 1, end);
return Head;
}
};