参考链接

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

题目描述

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

二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
右子树是通过数组中最大值右边部分递归构造出的最大二叉树。
返回有给定数组 nums 构建的最大二叉树。

解题思路

题目已经显式地说明了，应该用递归的方式构建最大二叉树。先确定最大值的索引，索引左边的和右边的再分别构建最大二叉树，如此递归即可。

代码

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = constructTree(nums, 0, nums.size());
        return root;
    }
    TreeNode* constructTree(vector<int>& nums, int start, int end)
    {
        if (start == end)
        {
            return nullptr;
        }
        int index = 0;
        int max_num = 0;
        for (int i = start; i < end; i ++)
        {
            if (nums[i] >= max_num)
            {
                max_num = nums[i];
                index = i;
            }
        }
        TreeNode* root = new TreeNode(nums[index]);
        root->left = constructTree(nums, start, index);
        root->right = constructTree(nums, index + 1, end);
        return root;
    }
};