每日一练：LeeCode-654、最大二叉树【二叉树+DFS+分治】

本文是力扣LeeCode-654、最大二叉树【二叉树+DFS+分治】学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

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

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

示例 1：
在这里插入图片描述

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。

示例 2：

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

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数互不相同

思路

本题的思路：找到不断更新区间的中的最大值，以这个最大值为根节点，并且以此为其左右子树的分界点，不断递归构造树结构

递归法

构造树采⽤的是前序遍历，因为先构造中间节点，然后递归构造左⼦树和右⼦树。

1、确定递归函数的参数和返回值

TreeNode qianBianLi(int[] nums,int left,int right)

2、确定终⽌条件

if(left>=right)return null; //不满足下标判断，直接返回null的子节点即可

3、确定单层递归的逻辑

先要找到数组中最⼤的值和对应的下标
最⼤的值构造根节点，并以当前根节点作为左子树递归的右边界、以当前根节点作为右子树递归的左边界来构建树结构。

        int maxIndexValue = left;   // 分割点下标：maxValueIndex
        for (int i=left+1;i<right;i++){
            if (nums[i]>nums[maxIndexValue])maxIndexValue=i;
        }

        TreeNode root = new TreeNode(nums[maxIndexValue]);  // 左闭右开：[left, maxValueIndex)
        root.left = qianBianLi(nums,left,maxIndexValue);    // 左闭右开：[maxValueIndex + 1, right)
        root.right = qianBianLi(nums,maxIndexValue+1,right);
        return root;

整体代码

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return qianBianLi(nums,0,nums.length);
    }

    // 在左闭右开区间[left, right)，构造⼆叉树
    TreeNode qianBianLi(int[] nums,int left,int right){
        if(left>=right)return null; //不满足下标判断，直接返回null的子节点即可

        int maxIndexValue = left;   // 分割点下标：maxValueIndex
        for (int i=left+1;i<right;i++){
            if (nums[i]>nums[maxIndexValue])maxIndexValue=i;
        }

        TreeNode root = new TreeNode(nums[maxIndexValue]);  // 左闭右开：[left, maxValueIndex)
        root.left = qianBianLi(nums,left,maxIndexValue);    // 左闭右开：[maxValueIndex + 1, right)
        root.right = qianBianLi(nums,maxIndexValue+1,right);
        return root;
    }
}