树与图中等1 种解法
#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]
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
解题主线
- 最大值下标天然切分左右子树。
- 传递区间可避免每层复制子数组。
解法 1：区间扫描分治
在半开区间内寻找最大值，并递归构造其左右区间。
-
时间复杂度： O(n²) 最坏；平衡切分时 O(n log n)
-
空间复杂度： O(h)，最坏 O(n)；不计输出树
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length);
}
private TreeNode build(int[] nums, int left, int right) {
// 递归状态表示待构造的半开区间 [left, right)
if (left >= right) return null;
int maximum = left;
for (int i = left + 1; i < right; i++) {
if (nums[i] > nums[maximum]) maximum = i;
}
// 区间最大值作为根，其下标自然分隔左右子树
TreeNode root = new TreeNode(nums[maximum]);
root.left = build(nums, left, maximum);
root.right = build(nums, maximum + 1, right);
return root;
}
}边界与易错点
- 顺序数组会让树退化，朴素扫描的最坏时间是 O(n²)。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q654_constructMaximumBinaryTree.java