教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕《算法通关手册AlgoNote》仓库中 docs/solutions/0600-0699/maximum-binary-tree.md 这一题解文档深入解析 LeetCode 0654「最大二叉树」的题意、递归分治构建思路与可运行的 Python 实现。读完本文你将掌握按区间最大值切分数组、递归构造二叉树这一类问题的通用套路并能将递归三步法、二叉树的递归定义与本题的边界处理细节左闭右开区间融会贯通同时理解它与单调栈、二叉搜索树、DFS 等相关知识点的内在联系。1. 题目链接与标签题目0654. 最大二叉树 - 力扣LeetCode标签栈、树、数组、分治、二叉树、单调栈难度中等本题同时出现在仓库的题解列表与分类目录中属于二叉树 递归/分治范畴的经典入门题也是后续 0998. 最大二叉树 II 的前置铺垫题。2. 题目大意给定一个不含重复元素的整数数组nums。根据该数组构建的「最大二叉树」定义如下二叉树的根节点是数组中的最大元素左子树是通过数组中最大值左边部分构造出的最大二叉树右子树是通过数组中最大值右边部分构造出的最大二叉树。要求根据给定的数组构建最大二叉树并返回该树的根节点。2.1 从定义读懂构造规则以nums [3, 2, 1, 6, 0, 5]为例手工推演一遍完整构造过程全区间[0, 6)的最大值是6下标 3故6成为根节点左半部分[0, 3)即[3, 2, 1]最大值是3作为6的左孩子3左侧无元素左侧为空3右侧[2, 1]最大值是2作为3的右孩子右半部分[4, 6)即[0, 5]最大值是5作为6的右孩子5左侧[0]作为其左孩子。最终得到树的结构6为根左子树3 - 2 - 1右子树5 - 0。可以看到最大值定位 左右递归正是本题的唯一构造法则。2.2 与二叉搜索树的区别二叉搜索树BST左子树所有节点值 根节点值 右子树所有节点值且中序遍历结果递增详见仓库 docs/05_tree/05_04_binary_search_tree.md最大二叉树仅要求根节点是当前区间的最大值左、右子树分别是左右子区间的最大二叉树不保证左子树整体小于根节点左子树内可能存在大于根节点左邻值、但仍小于根节点的元素反之右子树内元素也都小于根节点因为根是全局最大。因此最大二叉树不是二叉搜索树不能用 BST 的查找/插入套路必须走区间切分 递归路线。3. 解题思路递归分治3.1 核心思想最大二叉树的定义本身就是一个递归定义最大值左边部分构造出的最大二叉树与整个数组构造最大二叉树是结构相同、规模更小的子问题。这正是递归三步法中把大问题拆解为同构小问题的典型场景理论背景可参考仓库 docs/07_algorithm/07_02_recursive_algorithm.md写递推公式构建(nums[left:right]) 根(区间最大值) 左(构建(nums[left:maxIdx])) 右(构建(nums[maxIdx1:right]))确定终止条件区间为空left right时返回None翻译为代码定义递归函数、编写递归主体、加入终止判断。具体步骤定义left、right分别表示当前数组区间的左右边界左闭右开遍历当前区间[left, right)找到最大值所在下标max_value_index以nums[max_value_index]建立根节点root将区间拆分为[left, max_value_index)与[max_value_index 1, right)两部分分别递归建树将递归结果赋给root.left、root.right返回root。3.2 边界处理的关键左闭右开区间题解代码使用if left right: return None作为递归出口并采用左闭右开区间[left, right)初始调用为(nums, 0, len(nums))覆盖整个数组左子区间为[left, max_value_index)天然排除了根节点自身右子区间为[max_value_index 1, right)同样排除根节点当left right区间空或left right时终止避免无限递归。这种区间约定与 Python 切片nums[left:right]的语义一致写递归时不易出现±1 越界错误建议读者在同类区间分治题中沿用。4. 完整代码实现原题解文档给出的核心实现如下class Solution: def createBinaryTree(self, nums: List[int], left: int, right: int) - TreeNode: if left right: return None max_value_index left for i in range(left 1, right): if nums[i] nums[max_value_index]: max_value_index i root TreeNode(nums[max_value_index]) root.left self.createBinaryTree(nums, left, max_value_index) root.right self.createBinaryTree(nums, max_value_index 1, right) return root def constructMaximumBinaryTree(self, nums: List[int]) - TreeNode: return self.createBinaryTree(nums, 0, len(nums))4.1 逐段讲解代码段作用要点if left right: return None递归出口区间为空时返回空节点对应空数组构造空树max_value_index left初始化最大值下标从区间左端点开始扫描for i in range(left 1, right): ...线性扫描找最大值题目保证元素互不重复因此不存在相等元素的比较歧义root TreeNode(nums[max_value_index])建立根节点根节点值即当前区间最大值root.left .../root.right ...递归建左右子树左右区间均排除根节点自身constructMaximumBinaryTree对外入口以(0, len(nums))作为全区间调用递归函数其中TreeNode为力扣内置的二叉树节点类val、left、right三个属性无需额外定义。4.2 复杂度分析时间复杂度$O(n^2)$。每一层递归需要线性扫描当前区间找最大值在最坏情况下数组单调递增或单调递减每次切分后一侧区间为空递归树退化为链状总扫描次数约为 $n (n-1) \cdots 1 O(n^2)$。空间复杂度$O(n)$。递归调用栈的深度在最坏情况下为 $n$退化为链表形状的树空间开销与树高成正比。5. 进阶单调栈视角与本题的标签解读题目标签中包含栈、单调栈这说明本题还有更高效的非递归解法。其背后原理与仓库 docs/03_stack_queue_hash_table/03_02_monotone_stack.md 中的查找右侧/左侧第一个更大元素一脉相承最大二叉树中任意节点左侧最近的更大元素与右侧最近的更大元素中较小的一方即为该节点的父节点因此可以用单调递增栈在 $O(n)$ 时间内确定每个节点的父节点再按右子树挂更小、左子树挂更大的规则连线从而在线性时间内构建整棵树。从源码结构看docs/03_stack_queue_hash_table/03_02_monotone_stack.md提供了单调递增栈的标准模板while stack and num stack[-1]: stack.pop()读者可将其作为实现 $O(n)$ 解法的脚手架。作为对照暴力递归解法的 $O(n^2)$ 扫描与单调栈 $O(n)$ 扫描的差异也体现了用栈记录候选更大元素、避免重复扫描这一优化思想。6. 关联题目与延伸学习0998. 最大二叉树 II给定已构建好的最大二叉树根节点root和一个新值val要求在数组末尾追加val后重新构造。其递归解法只需沿右子树下探因为新值在数组末尾若val大于当前节点值则val成为新根、原树整体挂为左子树否则递归插入右子树。时间复杂度为 $O(h)$$h$ 为树高。本题可作为检验是否真正理解最大二叉树构造规则的进阶题。0104. 二叉树的最大深度与本题同属递归遍历树家族递推公式为max(左子树深度, 右子树深度) 1可用来巩固递归三步法。递归与分治的方法论基础递归算法、分治算法。树的遍历与还原专题二叉树遍历、二叉树还原。仓库中的完整题解索引位于 docs/solutions/0600-0699/index.mdLeetCode 题目总表与分类表可参考 docs/00_preface/00_05_solutions_list.md 与 docs/00_preface/00_06_categories_list.md。7. 总结LeetCode 0654「最大二叉树」的核心考点有三递归定义即解法——最大二叉树的定义本身就是递归的根为区间最大值、左右子树递归构造照抄定义即可写出正确递归区间边界约定——采用左闭右开区间[left, right)与left right出口能干净利落地处理空区间避免 ±1 越界复杂度认知——递归扫描法为 $O(n^2)$ 时间、$O(n)$ 空间而单调栈可优化到 $O(n)$进阶时值得一练。掌握本题后建议顺手完成 0998 题尾部插入场景并对比单调栈实现即可彻底吃透最大二叉树这一题族。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐WinUI 崩溃诊断指南四步拿到转储读懂堆栈WinUI 崩溃诊断指南四步拿到转储读懂堆栈 WinUIMicrosoft.UI.Xaml为 Windows 应用提供现代原生控件与 Fluent 设计风前端UI组件桌面应用LeetCode 257. Binary Tree Paths二叉树的所有路径Go 递归题解LeetCode 257. Binary Tree Paths二叉树的所有路径Go 递归题解 本篇技术指南围绕 LeetCode 第 257 题「Binar示例工程AlgoNote 算法题解LeetCode 0106 从中序与后序遍历序列构造二叉树递归分治全解析AlgoNote 算法题解LeetCode 0106 从中序与后序遍历序列构造二叉树递归分治全解析 本文是 AlgoNote「算法通关手册」二叉树还原专题教程文档知识库上一篇webpack-dev-server 修复页面加载期间抛出的运行时错误不再被初始握手误关闭 Overlay下一篇Windows安装包架构设计WiX Toolset在企业级软件分发中的完整解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考