数据结构拓展习题：最大二叉树

题目： 给定一个非空且无重复元素的整数数组A，它对应的“最大二叉树”T (A)定义为：

① T(A)的根为A中最大值元素；

② T(A)左子树为A中最大值左侧部分对应的“最大二叉树”；

③ T(A)右子树为A中最大值右侧部分对应的“最大二叉树”。

例如：A={3, 2, 1, 6, 0, 5}对应的“最大二叉树”T (A)如右图所示。

设计一个“最大二叉树”的构建算法，并分析最好情况、最坏情况下的时间和空间复杂性。

BiTree CreatBiggestBiTree(int* A, int start, int end)

{

       if (start > end)

              return NULL;

       int index = start;

       int max = A[start];

       for (int i = start; i <= end; i++)//查找数组索引范围内的最大元素

       {

              if (A[index] < A[i])

              {

                     index = i;

                     max = A[i];

              }

       }

       BiTree T = (BiTNode*)malloc(sizeof(BiTNode));

       if (!T)

              exit(OVERFLOW);

       T->data = max;

       T->lchild = CreatBiggestBiTree(A, start, index - 1);

       T->rchild = CreatBiggestBiTree(A, index + 1, end);

       return T;

}