最大二叉树构建算法：时间复杂度和空间复杂度分析

给定一个非空且无重复元素的整数数组A，它对应的'最大二叉树'T(A)定义为： ① T(A)的根为A中最大值元素； ② T(A)左子树为A中最大值左侧部分对应的'最大二叉树'； ③ T(A)右子树为A中最大值右侧部分对应的'最大二叉树'。

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

算法思路：

1. 找到数组A中的最大值maxVal；
2. 以maxVal为根节点创建一个二叉树；
3. 递归构建左子树和右子树，左子树根节点为maxVal左侧的最大值，右子树根节点为maxVal右侧的最大值。

最好情况下，数组A中的元素是有序的，每次递归都只需处理一半的元素，时间复杂度为O(nlogn)；空间复杂度为O(logn)，递归栈的深度为树的高度logn。

最坏情况下，数组A中的元素是倒序的，每次递归都需处理n-1个元素，时间复杂度为O(n^2)；空间复杂度为O(n)，递归栈的深度为n。

算法实现：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return buildTree(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* buildTree(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        TreeNode* root = new TreeNode(nums[maxIndex]);
        root->left = buildTree(nums, left, maxIndex - 1);
        root->right = buildTree(nums, maxIndex + 1, right);
        return root;
    }
};