【二叉树】LC 437.路径总和 III

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

437.路径总和 III

2、题目描述

二、个人思路整理

1、思路分析

思路1：前缀和 + 回溯

核心逻辑：

1. 前缀和概念：设从根节点到当前节点的路径节点值总和为curr_sum。如果路径上存在某个祖先节点，其对应的前缀和为curr_sum - targetSum，那么从该祖先节点的子节点到当前节点构成的路径和即为targetSum。
2. 哈希表记录：使用哈希表unordered_map<long long, int> prefix记录从根节点到当前路径上各个前缀和出现的频次。
3. 回溯恢复状态：因为树有分叉，在遍历完当前节点的左右子树并返回上一层时，必须将当前节点的前缀和计数-1，避免影响其他分支的计算。
4. 溢出注意：节点值累加可能会超过 32 位整型范围，前缀和变量需使用long long。

思路2：双重 DFS

核心逻辑：

1. 遍历树中的每一个节点作为路径的起点。
2. 对每个起点，向下 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_map<longlong,int>prefix;prefix[0]=1;// 初始化：前缀和为 0 的路径有 1 条（代表从根节点直接出发的情况）returndfs(root,0,targetSum,prefix);}private:intdfs(TreeNode*node,longlongcurrSum,inttargetSum,unordered_map<longlong,int>&prefix){if(!node){return0;}currSum+=node->val;intcount=0;// 查找是否存在前缀和为 currSum - targetSum 的祖先节点if(prefix.count(currSum-targetSum)){count+=prefix[currSum-targetSum];}// 将当前前缀和加入哈希表prefix[currSum]++;// 递归左右子树count+=dfs(node->left,currSum,targetSum,prefix);count+=dfs(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 为起点的有效路径数intcount=countFromNode(root,targetSum);// 2. 递归统计以左子树节点为起点，右子树节点为起点的有效路径数count+=pathSum(root->left,targetSum);count+=pathSum(root->right,targetSum);returncount;}private:// 以 node 为起点，向下连续累加寻找和为 sum 的路径数intcountFromNode(TreeNode*node,longlongsum){if(!node){return0;}intres=0;// 如果当前节点值刚好匹配剩余目标值，找到一条有效路径if(node->val==sum){res++;}// 继续向下累加左右子树（由于可能有负数节点，即使当前匹配了也要继续往下找）res+=countFromNode(node->left,sum-node->val);res+=countFromNode(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_map<long 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，作为边界条件的兜底。

算法变体与扩展：

• 路径总和 I（LeetCode 112）：判断是否存在从根节点到叶子节点的路径和为targetSum，是本题的简化版本，只需一次 DFS 即可。
• 路径总和 II（LeetCode 113）：找出所有从根节点到叶子节点、路径和为targetSum的路径，需要回溯记录路径节点，可对比理解回溯的用法。
• 二叉树的最近公共祖先（LeetCode 236）：同样是树上的路径问题，但关注的是节点关系而非路径和，可对比理解不同树问题的解题思路。
• 和为 K 的子数组（LeetCode 560）：一维数组版本的前缀和问题，与本题的核心思想完全一致，可对比理解前缀和在不同数据结构上的应用。

相关 LeetCode 例题：

• 112. 路径总和（简化版：判断是否存在根到叶子的路径和）
• 113. 路径总和 II（进阶版：找出所有满足条件的路径）
• 560. 和为 K 的子数组（一维前缀和思想）
• 236. 二叉树的最近公共祖先（树上的路径问题对比）