437 路径之和III
直接做法
pathSum表示返回二叉树中任意节点为起点和为targetSum的路径数,注意:这里的任意节点包括:
- 根节点
- 根节点的直接子节点
- 间接子节点
因此我们想到,遍历二叉树的每个节点,以这个节点为起点,计算和为targetSum的路径数,最后累加起来,就是结果
遍历的方式有很多,以最简单的前序遍历为例
那么我们的问题就变成了求解一个函数,这个函数负责计算以某个节点为起点,和为targetSum的路径数
为此我们定义了一个函数rootSum
- 该函数就是计算特定节点为起点的和为targetSum的路径数
-
计算方法:
- 如果当前节点root值为targetSum,表示我们找到了目标节点,路径数加一
- 如果当前节点root值不为targetSum,那么我们需要继续遍历当前节点的左子树和右子树,直到找到满足题意的路径
- 如果左/右子树存在节点node,使得root->n1->n2->...->node的和为targetSum,那么路径数加一
由于节点的值可以为负数,因此情况1和情况2可以同时成立,因此结果应该是两种情况的和
现在我们已经定义了函数rootSum,那么pathSum也就可以实现了:
- 本质是遍历二叉树,这里我们采用了前序遍历
- 处理每个节点后,遍历它的左子树和右子树
- 处理每个节点的方式:以每个节点作为起点,计算每个节点为起点的和为targetSum的路径数,即计算rootSum
/**
* 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) {}
* };
*/
class Solution {
private:
// 计算以某个节点为起点的路径数
// root->n1->n2->...->node
int rootSum(TreeNode* root, long targetSum){
if(!root)
return 0;
int res = 0;
// 如果当前节点值为targetSum
if(root->val == targetSum)
res++;
// 如果当前节点值不为targetSum
// 由于我们已经假设root一定包含在路径中
// 因此之后寻找路径需要更新targetSum
res += rootSum(root->left, targetSum - root->val);
res += rootSum(root->right, targetSum - root->val);
return res;
}
public:
// 注意数据范围,使用long
int pathSum(TreeNode* root, long targetSum) {
if(!root)
return 0;
int res = 0;
// 前序遍历框架
res += rootSum(root, targetSum);
// 路径不需要从根节点开始
// 每个节点都可以是路径的起点
// 因此每次调用pathSum都是同样的targetSum
res += pathSum(root->left, targetSum);
res += pathSum(root->right, targetSum);
return res;
}
};
时间复杂度:\(O(N^2)\),其中 N 为该二叉树节点的个数。对于每一个节点,求以该节点为起点的路径数目时,则需要遍历以该节点为根节点的子树的所有节点,因此求该路径所花费的最大时间为 O(N),我们会对每个节点都求一次以该节点为起点的路径数目,因此时间复杂度为 \(O(N^2)\)
空间复杂度:O(N),考虑到递归需要在栈上开辟空间。
优化做法
以每个节点为起点计算路径数,会包含很多重复的路径,例如:
- n1->n2->...->n7->n8
- n2->...->n7
假设这两条路径都符合和为targetSum,那么计算路径1会包含路径2的步骤,重复了路径2的计算
针对这种情况,我们可以联想到数组中的前缀和,问题在于二叉树如何实现前缀和。我们发现从根节点到叶子节点这条路径其实就对应一个数组,那么我们只需要将问题分解为每条根节点到叶子结点这条路径如何求解即可,再将最后结果累加
- 在深度优先遍历中,我们知道,遍历到叶子节点时会回溯,那么从根节点到叶子节点这条路径中,有多少条以某个节点为起点和为targetSum的路径数。在直接做法中,通过对每个节点求一次rootSum。在优化做法中,维护前缀和+哈希表避免重复计算
- 当节点回溯时,路径更新,因此哈希表也需要更新(哈希表去掉回溯节点对应前缀和的标记)
/**
* 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) {}
* };
*/
class Solution {
private:
unordered_map<long,int> hashMap;
int dfs(TreeNode* root, long pre, long targetSum){
if(!root)
return 0;
// 前序遍历
pre += root->val;
int res = 0;
// sum[i] - sum[j - 1] == targetSum
// -> sum[j - 1] == sum[i] - targetSum
if(hashMap.count(pre - targetSum))
res += hashMap[pre - targetSum];
// 为什么要恢复现场
// 因为遍历完当前节点会回溯,回溯意味着这条路径的和pre不存在
hashMap[pre]++;
res += dfs(root->left, pre, targetSum);
res += dfs(root->right, pre, targetSum);
hashMap[pre]--;
return res;
}
public:
int pathSum(TreeNode* root, long targetSum) {
if(!root)
return 0;
hashMap[0] = 1;
// 只需要遍历一次二叉树
return dfs(root, 0,targetSum);
}
};
复杂度分析
- 时间复杂度:O(N),其中 N 为二叉树中节点的个数。利用前缀和只需遍历一次二叉树即可。
- 空间复杂度:O(N)
总结
直接做法和优化做法本质上都是遍历一遍二叉树,遍历方式采用了前序遍历,区别在于如何处理根节点
-
处理根节点:计算根节点到叶子节点和为targetSum的路径数
-
直接做法:以根节点到叶子节点这条路径中的每个节点作为起点,计算该起点和为targetSum的路径数
-
优化做法:以根节点到叶子节点这条路径,使用前缀和 + 哈希表,只需遍历一次路径即可得到和为targetSum的路径数
-
类比于数组中
-
-
-
遍历左子树 + 遍历右子树
- 唯一需要注意的是,优化做法中,由于回溯,哈希表需要删除回溯元素