178.二叉树：最大二叉树（力扣）

代码解决

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {// 创建一个新的树节点，初始值为0TreeNode* node = new TreeNode(0);// 如果输入数组长度为1，直接赋值给根节点的值，并返回该节点if(nums.size()==1){node->val=nums[0];return node;}// 初始化最大值为0，索引为0int maxVal = 0;int index = 0;// 遍历数组找到最大值及其索引for(int i = 0; i < nums.size(); i++){if(nums[i] > maxVal){maxVal = nums[i];index = i;}}// 将最大值赋给根节点node->val = maxVal;// 如果最大值索引大于0，递归构建左子树if(index > 0){// 创建左子数组vector<int> vec(nums.begin(), nums.begin() + index);// 递归构建左子树node->left = constructMaximumBinaryTree(vec);}// 如果最大值索引小于数组长度减1，递归构建右子树if(index < (nums.size() - 1)){// 创建右子数组vector<int> vec1(nums.begin() + index + 1, nums.end());// 递归构建右子树node->right = constructMaximumBinaryTree(vec1);}// 返回构建的树节点return node;}
};

1. 首先创建一个新的树节点 node，其初始值为0。
2. 如果输入数组长度为1，直接将数组中的第一个元素赋值给根节点的值，并返回该节点。
3. 初始化最大值为0，索引为0。
4. 遍历数组，找到最大值及其索引。
5. 将最大值赋给根节点的值。
6. 如果最大值索引大于0，创建一个包含从数组开始到最大值索引的子数组，递归构建左子树。
7. 如果最大值索引小于数组长度减1，创建一个包含从最大值索引+1到数组结束的子数组，递归构建右子树。
8. 返回构建的树节点。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是数组中元素的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。