4.3 给定一个有序整数数组，元素各不相同按升序排列，编写一个算法，创建一棵高度最小的二叉查找树。

解答

想要使构建出来的二叉树高度最小，那么对于任意结点， 它的左子树和右子树的结点数量应该相当。比如，当我们将一个数放在根结点， 那么理想情况是，我们把数组中剩下的数对半分，一半放在根结点的左子树， 另一半放在根结点的右子树。我们可以定义不同的规则来决定这些数怎样对半分， 不过最简单的方法就是取得有序数组中中间那个数，然后把小于它的放在它的左子树， 大于它的放在它的右子树。不断地递归操作即可构造这样一棵最小高度二叉树。

与leetcode类似题目：https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

C++实现代码：

#include
     
      #include
      
       using namespace std;struct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};TreeNode* helper(vector
       
        ::iterator begin,vector
        
         ::iterator end){    TreeNode *root=NULL;    if(begin+1==end)        return new TreeNode(*begin);    if(begin>=end)        return NULL;    int mid=(end-begin)/2;    root=new TreeNode(*begin+mid);    root->left=helper(begin,begin+mid);    root->right=helper(begin+mid+1,end);    return root;}TreeNode* createAVL(vector
         
           &vec){    if(vec.empty())        return NULL;    return helper(vec.begin(),vec.end());}void inorder(TreeNode *root){    if(root)    {        inorder(root->left);        cout<
          
           val<<" "; inorder(root->right); }}int maxDepth(TreeNode *root){ if(root) { if(root->left==NULL&&root->right==NULL) return 1; int leftDepth=maxDepth(root->left); int rightDepth=maxDepth(root->right); return leftDepth>= rightDepth ?(leftDepth+1):(rightDepth+1); } return 0;}int main(){ vector
           
             vec= { 1,2,3,4,5,6,7,8,9,10}; TreeNode *root=createAVL(vec); inorder(root); cout<