654.最大二叉树

力扣题目地址(opens new window)

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

提示：

给定的数组的大小在 [1, 1000] 之间。

lass Solution {
public:
    TreeNode* dfs(vector<int>& nums){
        TreeNode* root = new TreeNode(0);
        if(nums.size() == 1){
            root->val = nums[0];
            return root;
        }
        //找最大值
        int maxnum = 0;
        int index = 0;
        for(int i = 0;i < nums.size();i++){
            if(nums[i] > maxnum){
                maxnum = nums[i];
                index = i;
            }
        }
        root->val = maxnum;
        if(index > 0 ){
            vector<int> leftnum(nums.begin(),nums.begin()+index);
            root->left = dfs(leftnum);
        }
        if(index < nums.size()-1){
            vector<int>rightnum(nums.begin()+index+1,nums.end());
            root->right = dfs(rightnum);
        }
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums);
    }
};