难度中等641
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 *最大二叉树* 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
1、递归
这道题通过递归来构造树的话，那么和前中序或者中后序构造树是一个思路的！只不过我们要多做一步就是查找 nums 在 [left, right] 范围的最大值，然后拿这个最大值去构建当前结点！注意构造树一般都是通过前序遍历来执行的！
class Solution {
public:
TreeNode* build(vector<int>& nums, int left, int right)
{
if(left > right)
return nullptr;
// 查找范围内最大的值
int Max = INT_MIN;
int maxindex = 0;
for(int i = left; i <= right; ++i)
{
if(nums[i] > Max)
{
Max = nums[i];
maxindex = i;
}
}
// 前序构造结点，然后递归左右子树
TreeNode* newnode = new TreeNode(Max);
newnode->left = build(nums, left, maxindex - 1);
newnode->right = build(nums, maxindex + 1, right);
return newnode;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
}; 但是这种方法，最坏的情况下就是 nums 单调递增或者递减，就类似于快速排序的最坏情况，时间复杂度高达 O()。
2、单调栈
这道题可以用单调栈来完成，但是下面我们选择了用 vector 和一个 top 变量来模拟栈，这样子的好处就是我们随时可以得到栈底的元素也就是 st[0] 而不用说用栈去不断的 pop 掉元素！
还记得我们讲过单调队列吗，通过控制队列单调递增或者递减来得到某个区间的最值，这道题也是一样，我们要获得的是这个数组中的最大值来构造当前结点，但是这样子的话每次去找次大的值，就又得遍历一遍，时间复杂度就是 O() ，所以我们考虑的是直接遍历每个结点，当前结点不一定是要最大值才能构建结点阿，只不过我们要改变一下构建结点的规则！
采用单调栈的基本思路是这样的：
1、如果栈顶元素大于待插入的元素，那么直接入栈。 2、如果栈顶元素小于待插入的元素，那么栈顶元素出栈。
当然，在对比两个节点大小和出入栈的同时，依然还是会根据题意，进行二叉树的构造。即：
1、如果栈顶元素大于待插入的元素，则：栈顶元素.right = 待插入元素。
2、如果栈顶元素小于待插入的元素，则：待插入元素.left = 栈顶元素。
下面 copy 一段题解，解释的非常清晰：
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> st(nums.size(), nullptr);
int top = 0; // 控制模拟栈数组的元素个数
for(int i = 0; i < nums.size(); ++i)
{
TreeNode* newnode = new TreeNode(nums[i]);
// 比栈顶元素大的情况
while(top > 0 && nums[i] > st[top - 1]->val)
{
st[top - 1]->right = newnode->left;
newnode->left = st[top - 1];
top--;
}
// 通过上面规定的比栈顶大的情况，现在剩下的就是比栈顶小的情况
if(top > 0)
st[top - 1]->right = newnode;
st[top++] = newnode;
}
return st[0];
}
};