654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:

1. The size of the given array will be in the range [1,1000].

---

给定一个数组，要求用数组元素创建一个最大树。最大树的含义是，根节点是数组中的最大元素，左子树是以数组中最大元素划分的左子数组递归构造最大树，右子树以右子数组递归构造最大树。

简单题，设计一个子数组makeTree(nums,left,right)，每次从区间[left,right]中找到最大元素，然后构造根节点，最后递归在左子数组和右子数组中构造最大树。

完整代码如下：

const int MINVAL = -999999999;

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

本代码提交AC，用时100MS。

我原本以为可以先求出前k项的最大值和后k项的最大值，后续构造最大树的时候只需要查找这两个最大值就可以，事实上这是不行的，因为用最大值划分之后，求最大值和最小值的区间就不是前k项或者后k项了，有可能是某个中间的子区间，所以行不通，只能用上述暴力方法了。