文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析思路1前缀和 回溯思路2双重 DFS2、解题代码思路1前缀和 回溯思路2双重 DFS三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接437.路径总和 III2、题目描述二、个人思路整理1、思路分析思路1前缀和 回溯核心逻辑前缀和概念设从根节点到当前节点的路径节点值总和为curr_sum。如果路径上存在某个祖先节点其对应的前缀和为curr_sum - targetSum那么从该祖先节点的子节点到当前节点构成的路径和即为targetSum。哈希表记录使用哈希表unordered_maplong long, int prefix记录从根节点到当前路径上各个前缀和出现的频次。回溯恢复状态因为树有分叉在遍历完当前节点的左右子树并返回上一层时必须将当前节点的前缀和计数-1避免影响其他分支的计算。溢出注意节点值累加可能会超过 32 位整型范围前缀和变量需使用long long。思路2双重 DFS核心逻辑遍历树中的每一个节点作为路径的起点。对每个起点向下 DFS 搜索所有可能的向下路径统计和为targetSum的路径数。2、解题代码思路1前缀和 回溯/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:intpathSum(TreeNode*root,inttargetSum){unordered_maplonglong,intprefix;prefix[0]1;// 初始化前缀和为 0 的路径有 1 条代表从根节点直接出发的情况returndfs(root,0,targetSum,prefix);}private:intdfs(TreeNode*node,longlongcurrSum,inttargetSum,unordered_maplonglong,intprefix){if(!node){return0;}currSumnode-val;intcount0;// 查找是否存在前缀和为 currSum - targetSum 的祖先节点if(prefix.count(currSum-targetSum)){countprefix[currSum-targetSum];}// 将当前前缀和加入哈希表prefix[currSum];// 递归左右子树countdfs(node-left,currSum,targetSum,prefix);countdfs(node-right,currSum,targetSum,prefix);// 回溯离开当前节点前恢复状态prefix[currSum]--;returncount;}};复杂度分析时间复杂度O ( N ) O(N)O(N)每个节点只遍历一次哈希表单次查找/更新为O ( 1 ) O(1)O(1)。空间复杂度O ( N ) O(N)O(N)最坏情况下树退化为链表哈希表和递归栈深度均为O ( N ) O(N)O(N)。思路2双重 DFS/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:// 遍历整棵树的每个节点作为起点intpathSum(TreeNode*root,inttargetSum){if(!root){return0;}// 1. 以当前 root 为起点的有效路径数intcountcountFromNode(root,targetSum);// 2. 递归统计以左子树节点为起点右子树节点为起点的有效路径数countpathSum(root-left,targetSum);countpathSum(root-right,targetSum);returncount;}private:// 以 node 为起点向下连续累加寻找和为 sum 的路径数intcountFromNode(TreeNode*node,longlongsum){if(!node){return0;}intres0;// 如果当前节点值刚好匹配剩余目标值找到一条有效路径if(node-valsum){res;}// 继续向下累加左右子树由于可能有负数节点即使当前匹配了也要继续往下找rescountFromNode(node-left,sum-node-val);rescountFromNode(node-right,sum-node-val);returnres;}};复杂度分析时间复杂度平衡二叉树为O ( N log N ) O(N \log N)O(NlogN)最坏情况退化成链表为O ( N 2 ) O(N^2)O(N2)。空间复杂度递归栈空间O ( H ) O(H)O(H)H HH为树高。三、知识风暴前缀和Prefix Sum是本题的核心通过记录从根节点到当前节点的路径节点值总和可以在O ( 1 ) O(1)O(1)时间内判断是否存在某个祖先节点到当前节点的路径和为targetSum从而避免双重 DFS 的重复遍历。算法核心思想前缀和定义设curr_sum为从根节点到当前节点的路径节点值总和若路径上存在某个祖先节点的前缀和为curr_sum - targetSum则从该祖先节点的子节点到当前节点构成的路径和即为targetSum。哈希表记录使用unordered_maplong long, int记录从根节点到当前路径上各个前缀和出现的频次实现O ( 1 ) O(1)O(1)时间内的查找与更新。回溯恢复状态因为树有分叉在遍历完当前节点的左右子树并返回上一层时必须将当前节点的前缀和计数-1避免影响其他分支的计算。常见对比前缀和 回溯 vs 双重 DFS前缀和 回溯这是本题的最优解法每个节点只遍历一次时间复杂度为O ( N ) O(N)O(N)利用哈希表记录路径上的前缀和配合回溯恢复状态代码简洁且高效。双重 DFS遍历树中的每一个节点作为路径的起点再对每个起点向下 DFS 搜索所有可能的向下路径。实现直观但平衡二叉树下时间复杂度为O ( N log N ) O(N \log N)O(NlogN)最坏情况退化成链表为O ( N 2 ) O(N^2)O(N2)存在重复遍历。适用场景当树结构较平衡且数据规模较小时双重 DFS 的代码更易理解当数据规模较大或树退化为链表时前缀和 回溯的优势更加明显。哈希表加速思想核心思想利用哈希表记录路径上出现过的前缀和及其频次在遍历过程中直接查表判断是否存在满足条件的路径无需每次从头遍历。与本题的联系本题的路径方向是向下的因此前缀和天然满足「祖先节点到当前节点」的路径和计算需求。若路径方向不固定如可以向上折返则前缀和思想不再适用需要改用其他策略。注意事项前缀和变量需使用long long因为节点值累加可能会超过 32 位整型范围同时需注意哈希表初始化为prefix[0] 1代表从根节点直接出发的情况。使用要点初始化prefix[0] 1是必须的它代表「前缀和为 0 的路径有 1 条」即从根节点直接出发、路径和为targetSum的情况。查找时机在将当前前缀和加入哈希表之前先查找curr_sum - targetSum是否存在于哈希表中避免将当前节点自身误算为路径终点。回溯恢复递归完左右子树后必须执行prefix[curr_sum]--恢复状态否则会影响兄弟分支的计算结果。空节点处理递归函数遇到空节点直接返回 0作为边界条件的兜底。算法变体与扩展路径总和 ILeetCode 112判断是否存在从根节点到叶子节点的路径和为targetSum是本题的简化版本只需一次 DFS 即可。路径总和 IILeetCode 113找出所有从根节点到叶子节点、路径和为targetSum的路径需要回溯记录路径节点可对比理解回溯的用法。二叉树的最近公共祖先LeetCode 236同样是树上的路径问题但关注的是节点关系而非路径和可对比理解不同树问题的解题思路。和为 K 的子数组LeetCode 560一维数组版本的前缀和问题与本题的核心思想完全一致可对比理解前缀和在不同数据结构上的应用。相关 LeetCode 例题112. 路径总和简化版判断是否存在根到叶子的路径和113. 路径总和 II进阶版找出所有满足条件的路径560. 和为 K 的子数组一维前缀和思想236. 二叉树的最近公共祖先树上的路径问题对比
