企业官网建设流程全解析

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，又来到了每日的刷题时间，学习的还是二叉树的相关知识，和我们前面学的二叉树的构建差不多，让我们一起看看吧。

摘要：

本文介绍了如何构建最大二叉树的算法。给定一个不重复的整数数组，通过递归方式构建二叉树：首先找到当前数组片段的最大值作为根节点，然后递归地在最大值左侧子数组构建左子树，在右侧子数组构建右子树。文章详细解析了递归构建过程，包括确定根节点、分割左右子数组、终止条件等关键步骤，并通过示例演示了构建过程。最后提供了Java实现代码，强调返回值在递归连接中的重要性。该算法采用前序遍历方式，时间复杂度为O(n^2)，适用于构建具有特定结构的二叉树。

题目背景：654.最大二叉树

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

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

返回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. 确定根节点：在当前的数组片段中，最大值就是这棵子树的根节点。

2. 分割左右：

   • 最大值左边的区间用来递归构建左子树。

   • 最大值右边的区间用来递归构建右子树。

3. 终止条件：当递归的起始索引left大于结束索引right时，说明没有元素了，返回null

第一步肯定就是找到数组的最大值，很容易实现，需要注意的是我们也需要找到最大值的索引，为了后续的数组划分。

第二步就是创建根节点，然后依次递归，很简单的思路。

举个例子

假设nums = [3,2,1,6,0,5]

第一次调用（构建整棵树）

java

build(nums, 0, 5) // left=0, right=5

在[0,5]范围内找到最大值：6在索引3

所以：

• 根节点 = 6

• 左子树范围：[0, 2]（6左边的元素：3,2,1）

• 右子树范围：[4, 5]（6右边的元素：0,5）

关键来了：

java

root.left = build(nums, 0, 2); // 用左边部分递归构建左子树 root.right = build(nums, 4, 5); // 用右边部分递归构建右子树

递归构建左子树（build(nums, 0, 2)）

现在处理[0,2]范围，即[3,2,1]：

• 找到最大值：3在索引0

• 根节点 = 3

• 左子树范围：[0, -1]（3左边没有元素）

• 右子树范围：[1, 2]（3右边：2,1）

java

root.left = build(nums, 0, -1); // left > right，返回 null root.right = build(nums, 1, 2); // 继续构建子树

图解整个过程

text

原始数组: [3, 2, 1, 6, 0, 5] ↑ 最大值6在第3位 步骤1: 6 / \ 左边[3,2,1] 右边[0,5] 步骤2: 处理左边 6 / \ 3 [0,5]待处理 / \ null [2,1]待处理 步骤3: 继续...最终得到: 6 / \ 3 5 \ / 2 0 \ 1

易错分析：

为什么参数是maxIndex - 1和maxIndex + 1

因为最大值作为根节点后：

• 左子树应该使用最大值左边的所有元素

• 左边元素的索引范围是[left, maxIndex - 1]

• 右子树应该使用最大值右边的所有元素

• 右边元素的索引范围是[maxIndex + 1, right]

这样就能确保：

1. 左子树只用左边的元素构建

2. 右子树只用右边的元素构建

3. 不会重复使用最大值本身

关于方法的返回值：

我们从栈的角度来理解：

// 第一次调用 build(0,5) TreeNode root = new TreeNode(6); // 在栈帧1中创建节点6 root.left = build(0,2); // 调用栈帧2，等待返回值 // ========== 进入栈帧2 ========== // 第二次调用 build(0,2) - 完全独立的方法调用 TreeNode root = new TreeNode(3); // 在栈帧2中创建节点3（不同的root变量！） root.right = build(1,2); // 调用栈帧3，等待返回值 // ========== 进入栈帧3 ========== // 第三次调用 build(1,2) TreeNode root = new TreeNode(2); // 在栈帧3中创建节点2 root.right = build(2,2); // 调用栈帧4 // ========== 进入栈帧4 ========== // 第四次调用 build(2,2) TreeNode root = new TreeNode(1); // 在栈帧4中创建节点1 return root; // 返回节点1给栈帧3 // ========== 回到栈帧3 ========== // 现在栈帧3得到了返回值 root.right = 节点1; // 栈帧3的root（节点2）的right指向节点1 return root; // 返回节点2给栈帧2 // ========== 回到栈帧2 ========== root.right = 节点2; // 栈帧2的root（节点3）的right指向节点2 return root; // 返回节点3给栈帧1 // ========== 回到栈帧1 ========== root.left = 节点3; // 栈帧1的root（节点6）的left指向节点3 return root; // 返回节点6给main

如果没有返回值

1. 无法建立连接：上一层无法拿到当前层创建的节点

2. 节点丢失：创建的节点只在当前方法内有效，方法结束后就丢失了

返回根节点的三个必要性：

1. 递归需要：父节点需要子节点返回的值来建立left/right连接

2. 调用者需要：main方法（力扣系统）需要根节点来验证答案

3. 数据不丢失：Java方法内的局部变量在方法结束后会销毁，必须通过返回值传递出去

题目答案：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { // 调用递归函数，初始范围为整个数组 return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { // 递归终止条件：区间无效，返回空节点 if (left > right) { return null; } // 1. 在当前区间 [left, right] 中找到最大值及其索引 int maxIndex = left; for (int i = left + 1; i <= right; i++) { if (nums[i] > nums[maxIndex]) { maxIndex = i; } } // 2. 创建根节点 TreeNode root = new TreeNode(nums[maxIndex]); // 3. 递归构建左子树（最大值左边的部分） root.left = build(nums, left, maxIndex - 1); // 4. 递归构建右子树（最大值右边的部分） root.right = build(nums, maxIndex + 1, right); return root; } }

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！