题目描述

对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。

给定一个有序序列int[] vals,请返回创建的二叉查找树的高度。

1 class MinimalBST  2 { 3     public: 4     TreeNode *BulidBST(vector
       
        vt,int l,int r) 5     { 6         if(l>r)return NULL; 7         int mid=l+(r-l)/2; 8         TreeNode *root=new TreeNode(vt[mid]); 9         root->left=BulidBST(vt,l,mid-1);10         root->right=BulidBST(vt,mid+1,r);11         return root;12     }13         14     int depth(TreeNode *root)15     {16         if(root==NULL)17         {18             return 0;19         }20         int l=depth(root->left)+1;21         int r=depth(root->right)+1;22         return ((l>r)?(l):(r));23     }    24         25     26     int buildMinimalBST(vector
        
          vals) 27     {28         int lf=0;29         int rg=vals.size()-1;30         TreeNode *T = BulidBST(vals,lf,rg);31         return depth(T);32     }33 };