企业官网建设流程全解析

河南郑州网站建设吕凡科技,wordpress 用户介绍,外贸网站推广的方法,房地产微网站建设栏目设计【LeetCode热题100】Java详解#xff1a;二叉树中的最大路径和#xff08;含递归解法与工程实践#xff09; 面向人群 正在准备技术面试#xff08;尤其是大厂后端、算法岗#xff09;的开发者已掌握二叉树基本遍历#xff0c;希望深入理解路径和问题的学习者刷 LeetCo…【LeetCode热题100】Java详解二叉树中的最大路径和含递归解法与工程实践面向人群正在准备技术面试尤其是大厂后端、算法岗的开发者已掌握二叉树基本遍历希望深入理解路径和问题的学习者刷 LeetCode「热题100」或「二叉树专题」的中级程序员对动态规划、递归思想感兴趣的工程人员 本文适合已能手写二叉树DFS遍历的读者。若对递归、全局变量不熟悉建议先完成 LeetCode 第124题的前置题目如第112题路径总和和第53题最大子数组和。关键词LeetCode 124、二叉树中的最大路径和、最大路径和、递归、深度优先搜索、树形DP、面试高频题、时间复杂度分析阅读前必须掌握的基础在深入阅读本文前请确保你已熟练掌握以下知识点二叉树的基本操作DFS遍历前序、中序、后序递归实现树遍历树节点的定义和基本操作动态规划思想状态定义和状态转移最大子数组和Kadane算法Java 基础全局变量的使用Math.max()函数递归栈的工作原理复杂度分析能分析 O(n) 时间复杂度理解递归栈空间复杂度✅ 推荐前置练习LeetCode 53最大子数组和LeetCode 112路径总和LeetCode 104二叉树的最大深度一、原题回顾题目链接124. 二叉树中的最大路径和题目描述二叉树中的路径被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点root返回其最大路径和。示例 1输入root [1,2,3] 输出6 解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6可视化树结构1 / \ 2 3示例 2输入root [-10,9,20,null,null,15,7] 输出42 解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42可视化树结构-10 / \ 9 20 / \ 15 7提示树中节点数目范围是[1, 3 * 10⁴]-1000 Node.val 1000二、原题分析2.1 核心概念理解路径的关键特性连续性路径必须是连续的节点序列相邻节点必须有边连接无重复同一个节点在路径中最多出现一次任意起点终点路径可以开始和结束于任意节点不一定过根最优路径可能完全在某个子树中2.2 问题的难点路径形状不确定路径可能是直线单向或折线通过根节点连接左右子树负数影响负值节点可能降低路径和需要决定是否包含全局最优 vs 局部最优需要同时维护全局最大值和局部贡献值2.3 与经典问题的关联这个问题实际上是最大子数组和在树结构上的扩展问题数据结构路径约束解法思想最大子数组和数组连续子数组Kadane算法最大路径和二叉树树中连续路径树形DP 递归关键洞察树中的路径可以看作是以某个节点为最高点的倒V形路径三、答案构思递归解法本题的经典解法是递归 全局变量体现了树形动态规划的思想。3.1 核心思想对于树中的每个节点我们需要考虑两种角色作为路径的最高点转折点路径从左子树上来经过当前节点再到右子树下去作为路径的一部分贡献者当前节点只能向上传递一条路径选择左或右子树中贡献更大的3.2 状态定义定义maxGain(node)函数含义以node为起点向下延伸的路径的最大贡献值约束路径必须包含node且只能选择左子树或右子树不能同时选3.3 状态转移对于节点node作为最高点的路径和node.val max(0, leftGain) max(0, rightGain)向上传递的贡献值node.val max(0, leftGain, rightGain)✅为什么取max(0, …)因为如果子树的贡献值为负我们宁愿不选择该子树贡献值为0四、完整答案与代码实现Java方法递归树形DP思路详解这是最经典的解法采用后序遍历的思想递归函数maxGain(node)计算以node为起点的最大贡献值全局变量maxSum记录全局最大路径和递归过程先递归计算左右子树的最大贡献值计算以当前节点为最高点的路径和更新全局最大值返回当前节点向上传递的最大贡献值关键技巧区分当前节点作为路径最高点和当前节点作为路径贡献者的不同角色Java 代码classSolution{// 全局变量记录最大路径和privateintmaxSumInteger.MIN_VALUE;publicintmaxPathSum(TreeNoderoot){maxGain(root);returnmaxSum;}/** * 计算以node为起点的最大贡献值 * param node 当前节点 * return 以node为起点向下延伸的最大路径和贡献值 */privateintmaxGain(TreeNodenode){if(nodenull){return0;}// 递归计算左右子树的最大贡献值// 如果贡献值为负则选择不包含该子树贡献值为0intleftGainMath.max(maxGain(node.left),0);intrightGainMath.max(maxGain(node.right),0);// 计算以当前节点为最高点的路径和// 路径左子树 - 当前节点 - 右子树intcurrentPathSumnode.valleftGainrightGain;// 更新全局最大路径和maxSumMath.max(maxSum,currentPathSum);// 返回当前节点向上传递的最大贡献值// 只能选择左子树或右子树中贡献更大的一个returnnode.valMath.max(leftGain,rightGain);}}执行过程图解示例2以root [-10,9,20,null,null,15,7]为例后序遍历顺序9 → 15 → 7 → 20 → -10 访问9叶节点: leftGain 0, rightGain 0 currentPathSum 9 0 0 9 maxSum max(-∞, 9) 9 返回贡献值 9 max(0,0) 9 访问15叶节点: currentPathSum 15 maxSum max(9, 15) 15 返回贡献值 15 访问7叶节点: currentPathSum 7 maxSum max(15, 7) 15 返回贡献值 7 访问20: leftGain max(15, 0) 15 rightGain max(7, 0) 7 currentPathSum 20 15 7 42 maxSum max(15, 42) 42 返回贡献值 20 max(15, 7) 35 访问-10: leftGain max(9, 0) 9 rightGain max(35, 0) 35 currentPathSum -10 9 35 34 maxSum max(42, 34) 42 返回贡献值 -10 max(9, 35) 25 最终结果42边界情况处理全负数情况输入[-3, -2, -1] 输出-1选择最大的单个节点执行过程每个节点的子树贡献值都是0因为负数被max(0, …)过滤每个节点的currentPathSum就是节点本身的值maxSum会记录最大的单个节点值单节点情况输入[5] 输出5五、代码分析5.1 关键设计决策全局变量 vs 返回值全局变量maxSum用于记录全局最优解递归函数返回值用于传递局部最优解这种分离使得逻辑清晰避免了复杂的返回值设计负数处理Math.max(maxGain(...), 0)确保只选择正贡献的子树这相当于如果子树拖后腿就不要它后序遍历必须先知道子树的信息才能计算当前节点的贡献后序遍历左→右→根保证了这一点5.2 代码健壮性空节点处理返回0符合贡献值的定义整数溢出题目范围较小-1000到1000不会溢出单节点处理正确处理只有一个节点的情况5.3 可读性优化虽然代码已经很简洁但我们可以添加更多注释来提高可读性classSolution{privateintglobalMaxInteger.MIN_VALUE;publicintmaxPathSum(TreeNoderoot){calculateMaxGain(root);returnglobalMax;}/** * 计算从当前节点向下延伸的最大路径和贡献值 * 注意这个路径只能向左或向右延伸不能分叉 */privateintcalculateMaxGain(TreeNodenode){if(nodenull){return0;// 空节点贡献为0}// 获取左右子树的最大贡献值负贡献视为0不选择intleftContributionMath.max(calculateMaxGain(node.left),0);intrightContributionMath.max(calculateMaxGain(node.right),0);// 计算通过当前节点的完整路径和可以分叉intpathThroughCurrentnode.valleftContributionrightContribution;// 更新全局最大路径和globalMaxMath.max(globalMax,pathThroughCurrent);// 返回当前节点能向上提供的最大贡献只能选择一边returnnode.valMath.max(leftContribution,rightContribution);}}六、时间复杂度与空间复杂度深度分析时间复杂度O(N)每个节点访问次数每个节点被访问恰好一次每次访问的操作常数时间操作比较、加法等总计O(N)其中N是树中节点的数量为什么不是O(N²)因为我们没有对每个节点都重新计算所有可能的路径而是通过递归一次性计算出所有信息。空间复杂度O(H)递归栈深度等于树的高度H最坏情况树退化为链表H N空间复杂度O(N)最好情况完全平衡树H log N空间复杂度O(log N)额外空间只有全局变量O(1)空间复杂度的关键递归调用栈的深度而不是存储的数据量。七、常见问题解答FAQQ1为什么需要全局变量不能直接在递归函数中返回最大路径和吗A因为递归函数需要返回向上传递的贡献值只能选择一边而最大路径和可能出现在任何位置包括以当前节点为最高点的完整路径。这两个值是不同的所以需要全局变量来记录全局最优解。Q2为什么要用Math.max(..., 0)直接相加不行吗A考虑负数的情况。如果左子树的最大贡献值是-5那么包含左子树只会让路径和更小。所以我们选择不包含左子树即贡献值为0。这相当于在路径中跳过负贡献的子树。Q3这个算法能处理所有负数的情况吗A可以。当所有节点都是负数时Math.max(..., 0)会让所有子树贡献值变为0每个节点的currentPathSum就是节点本身的值。maxSum会记录最大的那个负数这正是正确答案。Q4为什么返回值是node.val Math.max(leftGain, rightGain)而不是两者之和A因为返回值表示的是向上传递的贡献值路径只能向一个方向延伸要么向左要么向右不能分叉。如果返回两者之和就违反了路径的定义同一个节点不能出现两次。Q5能否不用全局变量而用其他方式实现A可以但会更复杂。例如可以让递归函数返回一个包含两个值的对象{最大路径和, 最大贡献值}。但这样代码会更冗长可读性更差。八、优化思路总结8.1 算法优化早期终止实际上无法早期终止因为负数的存在使得我们必须检查所有节点记忆化不需要因为每个节点只计算一次迭代替代递归可以用显式栈实现但代码复杂度增加收益不大8.2 代码优化避免全局变量备选方案classSolution{publicintmaxPathSum(TreeNoderoot){returnmaxPathSumHelper(root)[0];}// 返回 [全局最大路径和, 当前节点最大贡献值]privateint[]maxPathSumHelper(TreeNodenode){if(nodenull){returnnewint[]{Integer.MIN_VALUE,0};}int[]leftmaxPathSumHelper(node.left);int[]rightmaxPathSumHelper(node.right);intleftGainMath.max(left[1],0);intrightGainMath.max(right[1],0);intcurrentPathSumnode.valleftGainrightGain;intglobalMaxMath.max(currentPathSum,Math.max(left[0],right[0]));intcontributionnode.valMath.max(leftGain,rightGain);returnnewint[]{globalMax,contribution};}}8.3 性能优化数据类型使用int足够题目范围不会溢出函数调用开销递归调用不可避免但现代JVM优化得很好九、数据结构与算法基础知识点回顾9.1 树形动态规划Tree DP本题是树形DP的经典例子状态定义f(node) 以node为起点的最大贡献值状态转移f(node) node.val max(0, f(left), f(right))答案提取在状态转移过程中计算node.val max(0, f(left)) max(0, f(right))并更新全局答案9.2 最大子数组和Kadane算法的树形扩展数组版本Kadane算法intmaxSubArray(int[]nums){intmaxSoFarnums[0];intmaxEndingHerenums[0];for(inti1;inums.length;i){maxEndingHereMath.max(nums[i],maxEndingHerenums[i]);maxSoFarMath.max(maxSoFar,maxEndingHere);}returnmaxSoFar;}树版本的对应关系maxEndingHere↔ 节点的贡献值向上传递的值maxSoFar↔ 全局最大路径和数组的连续性 ↔ 树的连通性9.3 后序遍历的应用场景后序遍历适用于需要子树信息来决定父节点行为的场景应用场景说明删除树先删除子树再删除根计算子树大小子树大小 左子树大小 右子树大小 1最大路径和需要知道子树的最大贡献值平衡因子计算AVL树中需要子树高度十、面试官提问环节模拟Q你的解法中为什么时间复杂度是O(N)而不是O(N²)A因为每个节点只被访问一次我们在一次后序遍历中就计算出了所有必要的信息。不像暴力解法那样对每个节点都重新计算所有可能的路径。Q如果要求返回具体的路径而不仅仅是路径和你的解法需要如何修改A需要在更新maxSum的同时记录对应的路径。可以维护一个全局的bestPath列表并在递归函数中返回路径信息。具体来说递归函数需要返回{最大贡献值, 对应路径}然后在计算currentPathSum时构造完整的路径。Q能否处理节点值范围更大的情况比如接近Integer.MAX_VALUEA需要考虑整数溢出问题。可以将maxSum和相关变量改为long类型或者在每次加法前检查是否会溢出。但在实际面试中通常假设不会溢出。Q你的算法能扩展到N叉树吗A可以。对于N叉树我们需要找到子树中最大的两个正贡献值因为路径可以连接两个子树然后计算node.val top1 top2。向上传递的贡献值是node.val top1。Q如果路径必须包含根节点解法会有什么变化A那就简单多了只需要计算从根节点出发的最大路径和这可以通过简单的DFS实现不需要全局变量。但原题的难点就在于路径可以不经过根节点。十一、实际开发中的应用场景11.1 财务系统中的最优投资路径在投资组合树中找到收益最大的连续投资路径考虑风险调整后的收益负收益代表风险成本动态规划帮助找到最佳的投资时机序列11.2 网络路由优化在网络拓扑树中找到带宽最大的路径节点值代表链路质量或带宽容量负值可能代表拥塞或故障链路11.3 游戏开发技能树、任务链在技能树中找到属性加成总和最大的技能组合路径任务链中找到奖励总和最大的连续任务序列负值可能代表消耗的资源或冷却时间11.4 编译器优化AST抽象语法树中的表达式优化找出可以合并的常量表达式路径优化内存访问模式的连续性11.5 生物信息学基因序列树中的最优匹配路径蛋白质折叠结构中的能量最小化路径进化树中的特征相似性最大化路径十二、相关题目推荐题号题目关联点53最大子数组和一维版本Kadane算法112路径总和简单路径和问题437路径总和 III任意起点终点的路径和687最长同值路径路径长度而非路径和124本题树中最大路径和 学习路径建议53 → 112 → 437 → 124 → 687十三、总结与延伸13.1 核心思想提炼双重角色每个节点既是路径的潜在最高点也是路径的贡献者贪心选择只选择正贡献的子树负贡献直接舍弃全局 vs 局部全局最优解需要在局部计算过程中不断更新树形DP将复杂问题分解为子问题自底向上求解13.2 延伸思考动态树支持在线插入/删除节点动态维护最大路径和带约束的最大路径和路径长度限制、必须包含特定节点等多目标优化同时考虑路径和、路径长度、节点数量等多个指标并行计算对于超大树如何并行化最大路径和的计算13.3 面试答题建议展示完整的思考演进过程理解问题“路径可以是任意形状但必须连续且不重复对吗”分析特性解释路径的两种可能形状直线vs折线类比思考“这让我想到最大子数组和问题…”提出方案详细解释递归思路强调双重角色的概念代码实现写出清晰的代码解释关键行的作用边界讨论讨论全负数、单节点等特殊情况复杂度分析准确分析时间和空间复杂度最大路径和问题是树形动态规划的经典代表它完美展示了如何将一维的动态规划思想扩展到树形结构中。掌握这个问题的解法就掌握了处理树中最优路径问题的核心方法论