leetcode654. 最大二叉树

分析

1. 找到当前区间的最大值索引，构建根节点。
2. 递归构造左区间和右区间，生成root->left和root->right。
3. 当区间不合法时返回nullptr。

class Solution {
public:
    //得到最大值的位置
    int getMaxIndex(vector<int>& nums,int l,int r){
        int maxIndex=l;
        for(int i=l;i<=r;i++){
            if(nums[i]>nums[maxIndex])maxIndex=i;
        }
        return maxIndex;
    }
    //递归构建二叉树
    TreeNode* build(vector<int>& nums,int l,int r){
        if(l>r)return nullptr;
        int root_index=getMaxIndex(nums,l,r);
        TreeNode* root=new TreeNode(nums[root_index]);
        root->left=build(nums,l,root_index-1);
        root->right=build(nums,root_index+1,r);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums,0,nums.size()-1);
    }
};