知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 最大二叉树 ## 题目(LeetCode 654) 给定一个不重复的整数数组 `nums`,最大二叉树的构造规则: 1. 根节点是数组中的最大值 2. 左子树是最大值左边部分构造的最大二叉树 3. 右子树是最大值右边部分构造的最大二叉树 ``` 输入:nums = [3,2,1,6,0,5] 输出:[6,3,5,null,2,0,null,null,1] 6 / \ 3 5 \ / 2 0 \ 1 ``` ## 核心思路 这道题比 105/106 更简单,因为不需要两个数组配合,直接在一个数组里找最大值做根。 ``` nums = [3, 2, 1, 6, 0, 5] 1. 找最大值 6(index=3)→ 根节点 2. 左边 [3, 2, 1] → 递归构造左子树 3. 右边 [0, 5] → 递归构造右子树 左子树 [3, 2, 1]: 最大值 3(index=0)→ 根 左边 [] → null 右边 [2, 1] → 递归 右子树 [0, 5]: 最大值 5(index=1)→ 根 左边 [0] → 叶子 右边 [] → null ``` ## 代码 ```java class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int lo, int hi) { if (lo > hi) return null; // 找区间内最大值的索引 int maxIdx = lo; for (int i = lo + 1; i <= hi; i++) { if (nums[i] > nums[maxIdx]) maxIdx = i; } TreeNode root = new TreeNode(nums[maxIdx]); root.left = build(nums, lo, maxIdx - 1); root.right = build(nums, maxIdx + 1, hi); return root; } } ``` ## 为什么这道题特别适合理解构造树的套路? 因为它把构造树的三步骤展现得最清晰: 1. **确定根**:区间最大值 2. **划分左右**:最大值左边 / 右边 3. **递归构造**:对左右区间重复上述过程 105/106 题的"确定根"靠前序/后序,"划分左右"靠中序。本质完全一样。 ## 复杂度 - 时间:平均 O(n log n),最坏 O(n²)(数组有序时每次最大值在边界) - 空间:O(n)(递归栈) --- 上一篇:[02 - 从中序与后序遍历序列构造二叉树](./02-build-from-inorder-postorder.md) | 下一篇:[04 - 将有序数组转换为 BST](./04-sorted-array-to-bst.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入