企业官网建设流程全解析

网站开发与推广方向,怎么在百度推广自己的网站,公司注册网上怎么申请核名,软文营销的技巧有哪些【LeetCode热题100】Java详解#xff1a;路径总和 III#xff08;含O(N)暴力解与O(N)前缀和优化#xff09; 面向人群 正在准备技术面试#xff08;尤其是大厂后端、算法岗#xff09;的开发者已掌握二叉树基本遍历#xff0c;希望深入理解路径问题与前缀和技巧的学习者…【LeetCode热题100】Java详解路径总和 III含O(N²)暴力解与O(N)前缀和优化面向人群正在准备技术面试尤其是大厂后端、算法岗的开发者已掌握二叉树基本遍历希望深入理解路径问题与前缀和技巧的学习者刷 LeetCode「热题100」或「二叉树专题」的中级程序员对空间换时间、哈希表优化感兴趣的工程人员 本文适合已能手写二叉树DFS遍历的读者。若对递归、哈希表不熟悉建议先完成 LeetCode 第112题路径总和和第560题和为K的子数组。关键词LeetCode 437、路径总和 III、二叉树路径、前缀和、深度优先搜索、哈希表优化、递归、面试高频题、时间复杂度优化阅读前必须掌握的基础在深入阅读本文前请确保你已熟练掌握以下知识点二叉树的基本操作DFS遍历前序、中序、后序递归实现树遍历前缀和技术一维数组的前缀和概念LeetCode 560和为K的子数组Java 基础数据结构HashMap的基本操作put,get,getOrDefault递归栈的工作原理复杂度分析能区分 O(n)、O(n²) 时间复杂度理解空间换时间的思想✅ 推荐前置练习LeetCode 112路径总和LeetCode 113路径总和 IILeetCode 560和为K的子数组一、原题回顾题目链接437. 路径总和 III题目描述给定一个二叉树的根节点root和一个整数targetSum求该二叉树里节点值之和等于targetSum的路径的数目。路径的定义不需要从根节点开始不需要在叶子节点结束路径方向必须是向下的只能从父节点到子节点示例 1输入root [10,5,-3,3,2,null,11,3,-2,null,1], targetSum 8 输出3 解释和等于 8 的路径有 3 条如图所示。可视化树结构10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1三条路径5 → 35 → 2 → 1-3 → 11示例 2输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出3提示二叉树的节点个数的范围是[0,1000]-10⁹ Node.val 10⁹-1000 targetSum 1000二、原题分析2.1 核心要求解读路径灵活性起点和终点任意只要方向向下路径连续性必须是连续的父子节点链数值范围节点值可能很大需注意整数溢出计数而非列举只需要返回路径数量不需要具体路径2.2 关键挑战重复计算问题暴力解法会重复遍历相同子树路径起始点不确定每个节点都可能是路径起点负数影响由于存在负数路径和可能先增大后减小无法剪枝✅ 举例说明负数的影响路径10 → -5 → 3的和为8但中间过程10 → -5 5 8不能提前终止2.3 与经典路径问题的区别题目路径要求解法特点路径总和 I必须根到叶简单DFS可剪枝路径总和 II必须根到叶返回所有路径DFS 回溯路径总和 III任意起点终点向下即可需要考虑所有可能起点三、答案构思两种主流解法本题有两种经典解法体现了暴力 vs 优化的典型对比方法核心思想时间复杂度空间复杂度适用场景方法一双重DFS暴力对每个节点作为起点DFS找路径O(N²)O(N)小规模数据快速实现方法二前缀和 哈希表利用前缀和思想一次遍历解决O(N)O(N)大规模数据最优解 两种方法都是面试中的重要考点前者展示基础能力后者展示算法深度。四、完整答案与代码实现Java方法一双重DFS暴力解法思路详解这是最直观的解法分为两个层次外层DFS遍历每个节点将其作为潜在的路径起点内层DFSrootSum以当前节点为起点向下搜索所有可能的路径关键逻辑对于每个起点节点检查其值是否等于targetSum递归检查左子树和右子树目标值更新为targetSum - 当前节点值将所有起点的结果累加✅ 优点逻辑清晰易于理解和实现❌ 缺点时间复杂度高存在大量重复计算Java 代码classSolution{publicintpathSum(TreeNoderoot,longtargetSum){// 边界条件空树if(rootnull){return0;}// 以当前节点为起点的路径数intcurrentPathsrootSum(root,targetSum);// 递归处理左右子树作为起点的情况intleftPathspathSum(root.left,targetSum);intrightPathspathSum(root.right,targetSum);returncurrentPathsleftPathsrightPaths;}/** * 计算以root为起点路径和等于targetSum的路径数目 */privateintrootSum(TreeNoderoot,longtargetSum){if(rootnull){return0;}intpaths0;intvalroot.val;// 如果当前节点值等于目标值找到一条路径if(valtargetSum){paths;}// 递归搜索左右子树目标值减去当前节点值pathsrootSum(root.left,targetSum-val);pathsrootSum(root.right,targetSum-val);returnpaths;}}执行过程图解示例1以targetSum 8为例以10为起点 10 ≠ 8 10515 ≠ 8 105318 ≠ 8 1053321 ≠ 8 105217 ≠ 8 1052118 ≠ 8 10-37 ≠ 8 10-31118 ≠ 8 → 0条路径 以5为起点 5 ≠ 8 538 ✓ 53311 ≠ 8 527 ≠ 8 5218 ✓ → 2条路径 以-3为起点 -3 ≠ 8 -3118 ✓ → 1条路径 其他节点作为起点均无满足条件的路径 总计0213方法二前缀和 哈希表优化解法思路详解这个解法的灵感来源于LeetCode 560和为K的子数组将一维数组的前缀和思想扩展到树结构。核心洞察定义前缀和从根节点到当前节点路径上所有节点值的和如果存在两个节点A和BA是B的祖先且prefix[B] - prefix[A] targetSum那么从A的下一个节点到B的路径和就是targetSum算法步骤使用DFS遍历树维护当前路径的前缀和curr在哈希表中查找是否存在curr - targetSum如果存在说明找到了若干条满足条件的路径将当前前缀和加入哈希表递归处理左右子树回溯从哈希表中移除当前前缀和避免影响其他分支关键技巧哈希表存储的是当前路径上的前缀和频次Java 代码classSolution{publicintpathSum(TreeNoderoot,inttargetSum){if(rootnull){return0;}// 哈希表前缀和 - 出现次数MapLong,IntegerprefixMapnewHashMap();// 初始化空路径的前缀和为0出现1次prefixMap.put(0L,1);returndfs(root,prefixMap,0L,targetSum);}/** * DFS遍历计算满足条件的路径数目 * param node 当前节点 * param prefixMap 前缀和哈希表 * param curr 当前前缀和 * param targetSum 目标和 * return 路径数目 */privateintdfs(TreeNodenode,MapLong,IntegerprefixMap,longcurr,inttargetSum){if(nodenull){return0;}// 更新当前前缀和currnode.val;// 查找是否存在前缀和 curr - targetSumintpathsprefixMap.getOrDefault(curr-targetSum,0);// 将当前前缀和加入哈希表prefixMap.put(curr,prefixMap.getOrDefault(curr,0)1);// 递归处理左右子树pathsdfs(node.left,prefixMap,curr,targetSum);pathsdfs(node.right,prefixMap,curr,targetSum);// 回溯移除当前前缀和避免影响其他分支prefixMap.put(curr,prefixMap.get(curr)-1);returnpaths;}}执行过程图解详细示例以示例1为例targetSum 8初始化: prefixMap {0:1}, curr 0 访问10: curr 010 10 查找 10-82 → 不存在 → paths0 prefixMap {0:1, 10:1} 访问5: curr 105 15 查找 15-87 → 不存在 → paths0 prefixMap {0:1, 10:1, 15:1} 访问3: curr 153 18 查找 18-810 → 存在prefixMap[10]1 → paths1 prefixMap {0:1, 10:1, 15:1, 18:1} 访问3叶子: curr 183 21 查找 21-813 → 不存在 → paths0 返回后回溯移除21 访问-2: curr 18(-2) 16 查找 16-88 → 不存在 → paths0 返回后回溯移除16 回到5访问2: curr 152 17 查找 17-89 → 不存在 → paths0 prefixMap {0:1, 10:1, 15:1, 17:1} 访问1: curr 171 18 查找 18-810 → 存在prefixMap[10]1 → paths1 注意此时prefixMap中有18:1来自之前的3但现在是新的18 回到10访问-3: curr 10(-3) 7 查找 7-8-1 → 不存在 → paths0 prefixMap {0:1, 10:1, 7:1} 访问11: curr 711 18 查找 18-810 → 存在prefixMap[10]1 → paths1 总计1113为什么同一个前缀和18会出现多次因为它们来自不同的路径分支在回溯时会被正确清理不会互相干扰。五、代码分析与对比维度双重DFS方法一前缀和方法二时间复杂度O(N²)O(N)空间复杂度O(N)O(N)代码复杂度低中可读性高中适用数据规模N ≤ 100N ≤ 1000面试推荐度初级方案高级方案面试策略先实现方法一展示基础思路分析其时间复杂度问题提出方法二作为优化方案重点解释前缀和思想和回溯的必要性六、时间复杂度与空间复杂度深度分析时间复杂度分析方法一O(N²)外层DFS访问N个节点内层DFS每个节点作为起点时最坏需要遍历整个子树O(N)最坏情况链状树1 2 3 … N O(N²)方法二O(N)每个节点只被访问一次哈希表操作get/put平均O(1)总计O(N)性能对比N1000时方法一约需10⁶次操作方法二仅需10³次实际运行时间差距可达100倍以上空间复杂度分析两种方法都是O(N)但来源不同方法一递归栈深度O(h)最坏O(N)链状树方法二递归栈深度O(h)最坏O(N)哈希表大小O(h)因为只存储当前路径的前缀和✅关键区别方法二的哈希表大小等于当前递归深度而不是总节点数七、常见问题解答FAQQ1为什么方法二需要回溯移除前缀和A因为哈希表存储的是当前DFS路径上的前缀和。当从一个分支回溯到父节点时必须移除该分支的前缀和否则会影响另一个分支的计算。例如A / \ B C访问完B分支后如果不移除B路径上的前缀和计算C分支时会错误地认为这些前缀和仍然有效。Q2为什么初始化prefixMap.put(0, 1)A这处理了从根节点开始的路径。例如如果根到某节点的路径和正好等于targetSum那么curr - targetSum 0需要在哈希表中找到0的存在。Q3节点值范围很大会不会整数溢出A会的题目中节点值范围是[-10⁹, 10⁹]1000个节点最大和为10¹²超过int范围约2×10⁹。所以代码中使用long类型存储前缀和。Q4如果要求路径必须包含至少一个节点怎么办A当前解法已经满足这个要求因为我们只在访问实际节点时才计算路径。空路径前缀和0只是作为辅助计算存在。Q5能否用BFS替代DFSA理论上可以但实现更复杂。因为BFS无法自然维护从根到当前节点的路径信息需要额外存储路径或前缀和数组。八、优化思路总结8.1 时间优化核心前缀和思想将O(N²)降为O(N)哈希表快速查找避免重复计算一次遍历每个节点只处理一次8.2 空间优化及时回溯控制哈希表大小为O(h)而非O(N)使用long类型避免整数溢出导致的错误8.3 代码健壮性优化边界处理空树、单节点等特殊情况类型安全使用long防止溢出异常处理虽然题目保证输入有效但生产代码应更严谨九、数据结构与算法基础知识点回顾9.1 前缀和的核心思想前缀和用于快速计算任意区间和数组: [a₀, a₁, a₂, ..., aₙ] 前缀和: [s₀, s₁, s₂, ..., sₙ] 其中 sᵢ a₀a₁...aᵢ 区间[i,j]的和 sⱼ - sᵢ₋₁在树结构中“区间变成了路径段”。9.2 回溯算法的本质回溯 试错 撤销在本题中试错将当前前缀和加入哈希表撤销从哈希表中移除当前前缀和这是处理路径相关问题的标准模式。9.3 哈希表在算法中的作用哈希表在这里扮演了记忆化的角色记录历史状态前缀和快速查询是否存在满足条件的历史状态实现了空间换时间的经典优化十、面试官提问环节模拟Q你的前缀和解法中为什么哈希表的大小是O(h)而不是O(N)A因为我们在DFS过程中哈希表只存储从根节点到当前节点路径上的前缀和。当回溯时我们会移除当前节点的前缀和。因此哈希表中的元素数量始终等于当前递归深度也就是树的高度h。Q如果targetSum为0你的解法还正确吗A是的。例如路径5 → -5的和为0算法会正确计算。初始化prefixMap.put(0,1)也确保了从根开始的零和路径被正确计数。Q能否不用回溯而是在每次递归时传入新的哈希表副本A可以但这样空间复杂度会变成O(N²)因为每个递归调用都要复制整个哈希表。回溯的方式更节省空间。Q如何修改代码来返回所有满足条件的路径而不仅仅是数量A需要维护当前路径列表在找到满足条件的路径时将其复制保存。同时要处理路径重叠的问题确保每条路径都是独立的。十一、实际开发中的应用场景11.1 日志分析系统分析用户行为路径找出特定操作序列例如用户从登录到购买的路径中某些中间步骤的耗时总和11.2 金融交易监控监控交易链条中的资金流动找出金额总和达到特定阈值的交易路径反洗钱系统中的可疑资金流检测11.3 网络路由优化在网络拓扑树中找出延迟总和满足SLA要求的路径CDN节点选择中的成本优化11.4 游戏开发技能树、任务链技能树中找出属性加成总和达到特定值的技能组合任务链中经验或奖励总和的计算11.5 编译器优化AST抽象语法树中的表达式优化找出常量折叠机会多个常量相加等于目标值十二、相关题目推荐题号题目关联点112路径总和基础版本根到叶113路径总和 II返回所有路径560和为K的子数组前缀和经典题523连续的子数组和前缀和模运算974和可被K整除的子数组前缀和变种437本题树结构前缀和 学习路径建议112 → 113 → 560 → 437十三、总结与延伸13.1 核心思想提炼暴力解法展示问题理解但效率低下前缀和优化将树路径问题转化为数组子数组问题回溯技巧维护路径状态的关键空间换时间哈希表存储历史状态避免重复计算13.2 延伸思考多目标路径同时查找多个targetSum的路径路径长度限制要求路径包含恰好k个节点动态树支持在线插入/删除节点动态维护路径计数并行处理对于超大树如何并行化路径搜索13.3 面试答题建议展示完整的思考演进过程理解问题“路径可以任意起点终点但必须向下对吗”暴力方案提出双重DFS分析其O(N²)复杂度优化洞察“这让我想到数组的前缀和问题…”详细解释说明前缀和在树中的应用强调回溯的必要性边界讨论处理空树、整数溢出、负数等情况复杂度对比清晰说明两种方法的优劣算法优化的本质是在理解问题本质的基础上用合适的数据结构消除重复计算。掌握前缀和思想你就拥有了处理区间和、路径和问题的通用钥匙