LeetCode 654. 最大二叉树，【难度：中等；通过率：82.6%】，这道题的描述本身就是一份递归的构造方式，我们的任务就是将这份描述优雅地 翻译成代码；且思路类似 “由中序与前序/后序遍历结果构建二叉树”，参考：

• leetcode105深度解析：从前序与中序遍历序列构造二叉树
• leetcode106深度解析：从中序与后序遍历序列构造二叉树

一、 题目描述

给定一个不含重复元素的整数数组 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] 构建出的最大二叉树

示例 2:

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

---

二、 核心思路：分而治之与递归构造

题目的定义已经为我们指明了道路——递归。构建整棵树的过程，和构建其任意子树的过程，遵循着完全相同的规则，只是处理的数组范围不同。这就是典型的“分而治之”思想

我们可以将构建过程分解为三步：

1. 找到根节点：在当前需要处理的数组范围内，找到最大值及其索引。这个最大值就是当前子树的根节点
2. 构建左子树：对最大值左边的子数组，递归地执行相同的构建过程，并将返回的根节点作为当前根节点的左孩子
3. 构建右子树：对最大值右边的子数组，递归地执行相同的构建过程，并将返回的根节点作为当前根节点的右孩子

这个过程会一直持续下去，直到需要处理的子数组为空，此时返回 null，递归终止

三、代码实现与深度解析

直观解法就是定义一个辅助递归函数，该函数接收数组和需要处理的索引范围 [left, right] 作为参数

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {// 调用辅助递归函数，初始范围为整个数组return build(nums, 0, nums.length - 1);}/*** 辅助递归函数：在指定的数组范围 [left, right] 内构建最大二叉树* @param nums  原始数组* @param left  当前处理范围的左边界（包含）* @param right 当前处理范围的右边界（包含）* @return 构建好的子树的根节点*/private TreeNode build(int[] nums, int left, int right) {// 步骤 1: 定义递归终止条件// 如果左边界大于右边界，说明当前范围为空，无法构建节点if (left > right) {return null;}// 步骤 2: 在当前范围 [left, right] 内找到最大值的索引int maxIndex = -1;int maxValue = Integer.MIN_VALUE;for (int i = left; i <= right; i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}}// 步骤 3: 创建根节点TreeNode root = new TreeNode(maxValue);// 步骤 4: 递归构建左子树// 左子树的范围是 [left, maxIndex - 1]root.left = build(nums, left, maxIndex - 1);// 步骤 5: 递归构建右子树// 右子树的范围是 [maxIndex + 1, right]root.right = build(nums, maxIndex + 1, right);// 步骤 6: 返回当前构建好的根节点return root;}
}

---

四、 关键点与复杂度分析

• 递归函数的定义：build(nums, left, right) 的定义非常关键。它清晰地界定了每次递归需要处理的子问题——在 nums 数组的 [left, right] 区间内构建最大二叉树
• 寻找最大值：在每个递归步骤中，核心操作都是遍历当前子数组以找到最大值。这是主要的耗时部分
• 时间复杂度：在最坏的情况下（例如，数组是升序或降序排列的），树会退化成一个链表。每次寻找最大值的操作都需要扫描近乎整个子数组，总的时间复杂度为 O(N) + O(N-1) + … + O(1) = O(N²)
• 空间复杂度：空间开销主要来自递归调用栈。栈的深度取决于树的高度 H。在最坏情况下（退化为链表），树的高度为 N，因此空间复杂度为 O(N)。在平均情况下（树比较平衡），高度为 O(log N)，空间复杂度为 O(log N)

---

五、拓展解法

这道题的朴素递归解法时间复杂度是 O(N²)，有没有优化的可能呢？

答案是肯定的。瓶颈在于每次都需要线性扫描来寻找最大值。如果我们能用更高效的方式在数组的一个区间内找到最大值，就能优化性能。例如，使用单调栈可以在 O(N) 的时间内完成整个构建过程。但这需要更复杂的逻辑，因为它将树的构建过程从 “递归分解” 变为了 “迭代构建”，参考代码如下：

单调栈解法

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {if (nums == null || nums.length == 0) {return null;}// 使用数组（刷题环境显然需要追求极致性能，别用Stack）模拟栈// 存储 TreeNode 引用// 栈的大小最大为 nums.lengthTreeNode[] stack = new TreeNode[nums.length];int top = -1; // 栈顶指针，初始化为 -1 表示栈空for (int num : nums) {TreeNode node = new TreeNode(num); // 创建当前节点// 步骤 1: 处理栈顶元素 (pop)// 如果栈不为空，且栈顶元素的值小于当前节点的值// 那么栈顶元素应该成为当前节点的左孩子while (top != -1 && stack[top].val < node.val) {node.left = stack[top]; // 栈顶元素成为当前节点的左孩子top--; // 弹出栈顶元素}// 步骤 2: 连接当前节点的右孩子 (peek)// 如果栈不为空，且栈顶元素的值大于当前节点的值// 那么当前节点应该成为栈顶元素的右孩子if (top != -1) {stack[top].right = node; // 当前节点成为栈顶元素的右孩子}// 步骤 3: 当前节点入栈 (push)top++;stack[top] = node;}// 循环结束后，栈底（即 stack[0]）的元素就是整棵树的根节点// 因为它是最后一个入栈的，且没有比它更大的元素让它弹出或成为右孩子return stack[0]; }
}

两种解法对比

	递归构建 (朴素、直观解法)	单调栈 (O(N) 优化解法)
核心思路	分而治之：找到当前范围最大值作为根，递归处理左右子数组	利用结构：通过维护一个单调递减栈，一次遍历确定每个节点的左右孩子
构建过程	1. 遍历当前子数组找最大值 2. 创建根节点 3. 递归构建左子树 4. 递归构建右子树	1. 遍历数组元素，创建节点 curr 2. 栈顶小于 curr，弹出并作为 curr 的左孩子 3. 栈顶大于 curr，curr 作为栈顶的右孩子 4. curr 入栈
时间复杂度	O(N²)：每次递归都可能线性扫描子数组找最大值	O(N)：每个元素最多入栈一次、出栈一次，哈希表操作平均 O(1)
空间复杂度	O(N)：递归栈深度最坏为 N (退化为链表)	O(N)：栈中最多存储 N 个节点 (最坏情况)
代码可读性	高：与题目定义高度吻合，直观易懂	中等/低：逻辑较为抽象，需要理解单调栈的特性和指针连接规则
理解难度	较低，适合初学者入门递归	较高，需要对栈、树结构和相对大小关系有深入理解
底层实现	递归函数调用栈	通常使用数组 或 Deque (如 ArrayDeque) 模拟栈；不建议使用Stack
缺点	效率低，可能导致超时	逻辑复杂，不易一次性写对