1.问题

654. 最大二叉树 - 力扣（LeetCode）

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

2.思路

        构建最大二叉树就是找到数组中最大的值作为根节点，然后将数组分为左右区间，再找到各自区间的最大值作为左右子节点。直到构建完二叉树。实现步骤如下：

        1.判断二叉树是否完成构建。

        2.遍历整个数组找到最大值的下标作为根节点。

        3.根据下标分割左右区间，递归遍历构建二叉树。

3.代码实现

 TreeNode* traversal(vector<int>& nums,int left,int right)
    {
        //1.判断是否完成构建
        if(left>=right) return nullptr;

        //2.找最大值对应的下标，构建根节点
        int maxValueIndex = left;
        for(int i=left+1;i<right;i++){
            if(nums[i]>nums[maxValueIndex]) maxValueIndex = i;
        }
        TreeNode* root = new TreeNode(nums[maxValueIndex]);

        //3、根据下标分割区间并递归构建二叉树
        root->left = traversal(nums,left,maxValueIndex);
        root->right = traversal(nums,maxValueIndex+1,right);

        return root;
    }