654. 最大二叉树
给定一个不重复的整数数组 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]
[思路]
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
- 确定递归函数的参数和返回值
参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
TreeNode constructMaximumBinaryTree(int[] nums);
- 确定终止条件
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
TreeNode node = new TreeNode(0); if (nums.length == 1) { node.val = nums[0]; return node; }
- 确定单层递归的逻辑
1、先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。
int maxValue = 0; int maxValueIndex = 0; for (int i = 0; i < nums.length; i++) { if(nums[i] > maxValue) { maxValue = nums[i]; maxValueIndex = i; } } TreeNode root = new TreeNode(maxValue);
- 2、最大值所在的下标左区间构造左子树
这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
if (maxValueIndex > 0) { node.left = constructMaximumBinaryTree(nums, leftIndex, maxValueIndex); }
- 3、最大值所在的下标右区间构造右子树
判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。
if (maxValueIndex < (nums.size() - 1)) { node.right = constructMaximumBinaryTree(nums, maxValueIndex, nums.length); }
- 综合代码如下：
class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return constructMaximumBinaryTree1(nums, 0, nums.length); } public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) { if (rightIndex - leftIndex < 1) { // 没有元素了 return null; } if (rightIndex - leftIndex == 1) { //只有一个元素 return new TreeNode(nums[leftIndex]); } int maxIndex = leftIndex; // 最大值的数组下标 int maxValue = nums[maxIndex]; // 最大值 for (int i = leftIndex + 1; i < rightIndex; i++) { if (nums[i] > maxValue) { maxIndex = i; maxValue = nums[i]; } } TreeNode root = new TreeNode(maxValue); // 根据maxIndex划分左右子树 root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex); root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex); return root; } }
