leetcode_654. Maximum Binary Tree

https://leetcode.com/problems/maximum-binary-tree/

给定数组A，假设A[i]为数组最大值，创建根节点将其值赋为A[i]，然后递归地用A[0,i-1]创建左子树，用A[i+1，n]创建右子树。

---

 

使用vector的assign函数,该函数的特性：

Any elements held in the container before the call are destroyed and replaced by newly constructed elements (no assignments of elements take place).
This causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.

---

 

class Solution
{
public:

    TreeNode* constructMaximumBinaryTree(vector<int>& nums)
    {
        vector<int>::iterator maxiter,iter=nums.begin();
        int maxn=INT_MIN,len=nums.size();
        while(iter!=nums.end())
        {
            if(*iter>maxn)
            {
                maxn=*iter;
                maxiter=iter;
            }
            iter++;
        }
        vector<int> lnums,rnums;
        TreeNode *node = new TreeNode(maxn);
        if(maxiter!=nums.begin())
        {
            lnums.assign(nums.begin(),maxiter);
            node->left = constructMaximumBinaryTree(lnums);
        }
        if(maxiter!=nums.end()-1)
        {
            rnums.assign(maxiter+1,nums.end());
            node->right = constructMaximumBinaryTree(rnums);
        }
        return node;
    }
};

 

因为assign函数的特性是，每次给vector赋值都会自动销毁原先vector中的对象，虽然这里使用的是c++内置类型，但是多少还是会有开销。所以又写了一个不使用assign的版本。

class Solution
{
public:

    TreeNode* constructMaximumBinaryTree(vector<int>& nums)
    {
        return buildTree(nums, 0, nums.size()-1);
    }
    TreeNode* buildTree(vector<int>& nums, int l, int r)
    {
        if(l > r)
            return NULL;
        if(l == r)
        {
            TreeNode* node = new TreeNode(nums[l]);
            return node;
        }
        int max_n = INT_MIN, max_index = l;
        for(int i=l; i<=r ; i++)
            if(nums[i]>max_n)
            {
                max_n = nums[i];
                max_index = i;
            }
        TreeNode* root = new TreeNode(max_n);
        root->left = buildTree(nums, l, max_index-1);
        root->right = buildTree(nums, max_index+1, r);
        return root;
    }
};