给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例：
输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：6 / \ 3 5 \ / 2 0 \ 1
提示：
- 给定的数组的大小在 [1, 1000] 之间。
好久没看过树了，这道题完全没有思路，这是讨论区的思路。
递归套路三部曲：
- 找终止条件：当
l>r时，说明数组中已经没元素了，自然当前返回的节点为null。 - 每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的
root节点。 - 一次递归做了什么：找当前范围为
[l,r]的数组中的最大值作为root节点，然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树。
class Solution {
public:
int findMax(vector<int>& nums, int l, int r){
int maxIndex = l;
for(int i=l+1;i<=r;i++){
if(nums[i] > nums[maxIndex]){
maxIndex = i;
}
}
return maxIndex;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return maxTree(nums, 0, nums.size()-1);
}
TreeNode* maxTree(vector<int>& nums, int l, int r){
if(l>r){
return NULL;
}
int maxIndex = findMax(nums, l, r);
TreeNode *root = new TreeNode(nums[maxIndex]);
root->left = maxTree(nums, l, maxIndex-1);
root->right = maxTree(nums, maxIndex+1, r);
return root;
}
};
