【二叉树】最大二叉树

做题思路：切割数组，递归解决

递归结束条件：传入数组大小为0

1.遍历数组，得到最大元素。根据此元素创立结点，左右孩子设置为NULL

2.将数组以该最大元素为分割线分为左数组和右数组，求出左右数组的大小

3.递归进入左右数组。将左数组的结果作为左孩子，将递归右数组的结果作为右孩子

4.返回根结点

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
    // 递归结束条件：传入数组大小为0
    if(!numsSize)
        return NULL;
    // 1.遍历数组，得到最大元素。根据此元素创立结点，左右孩子设置为NULL
    int i;
    int index = -1;
    int max = -1;
    for(i = 0; i < numsSize; i++) {
        if(nums[i] > max) {
            index = i;
            max = nums[i];
        }
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = max;
    root->left = NULL;
    root->right = NULL;
    // 2.将数组以该最大元素为分割线分为左数组和右数组，求出左右数组的大小
    int leftNum = index;
    int rightNum = numsSize - index - 1;

    int* leftArr = nums;
    int* rightArr = nums + leftNum + 1;
    // 3.递归进入左右数组。将左数组的结果作为左孩子，将递归右数组的结果作为右孩子
    root->left = constructMaximumBinaryTree(leftArr, leftNum);
    root->right = constructMaximumBinaryTree(rightArr, rightNum);
    // 4.返回根结点
    return root;
}