题干:
代码:
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 1)return new TreeNode(nums[0]);int maxvalue = INT_MIN;int maxindex;for(int i = 0; i < nums.size(); i++){if(nums[i] > maxvalue){maxindex = i;maxvalue = nums[i];}}TreeNode* node = new TreeNode(maxvalue);if(maxindex > 0){vector<int> leftvec(nums.begin(), nums.begin() + maxindex);node -> left = constructMaximumBinaryTree(leftvec);}if(maxindex < nums.size() - 1){vector<int> rightvec(nums.begin() + maxindex + 1, nums.end());node -> right = constructMaximumBinaryTree(rightvec);}return node;}
};
要点:①两个if判断来构造左右子树,maxindex > 0 说明左侧数组长度大于等于1,maxindex < nums.size() - 1 说明右侧数组长度大于等于1。所以能成功构造。
②用迭代器构造数组,比如构造从nums开头到nums[3]的数组就用vector<int> newvec(nums.begin(), nums.begin() + 3); 从nums[3]再到nums末尾就是vector<int> newvec(nums.begin() + 3, nums.end())。总之构造的两侧区间都必须要有begin与end的存在。
③if分支下分别递归调用生成左右子树。