2024 7/20 一如既往的热,似乎已然习惯,昨晚睡眠还不错,特别是梦到了想见的人,有位女性朋友之前对我说,梦到了一个人就是在遗忘,是的,有些道理。那么,伴随着陶喆的《寂寞的季节》,我要开始做题了!
Anyway,我心中的陶喆top3
《Melody》、《寂寞的季节》、《二十二》。
1、题目描述
2、算法分析
遇到树相关的题目,就会想到那两个搜索遍历,BFS和DFS。这道题要求很明晰,给定一个目标值targetSum,求节点值和等于targetSum的路径数,要求限定也就是如题目所述。由于题目限定条件,那么我们遍历树的方式就只剩下DFS(深度优先搜索了),可以想到的是,遍历所有可能的路径、将符合要求的路径记录返回即可。
算法思想:
- 递归遍历:通过递归地遍历二叉树的每个节点,确保所有可能的路径都被检查到。
- 路径和的计算:对于每个节点,计算以该节点为起点的所有路径的和,并检查是否有任何路径的和等于给定的 targetSum。
3、代码
public int pathSum(TreeNode root, int targetSum) {
// 如果当前节点为空,说明已经到达叶子节点的下一层(即不存在),则返回0,因为没有路径可以形成
if(root == null){
return 0;
}
// 调用rootSum函数计算以当前节点为根的子树中,有多少条路径的和等于targetSum
int res = rootSum(root, targetSum);
// 递归调用pathSum函数,分别计算左子树和右子树中满足条件的路径数量
res += pathSum(root.left, targetSum);
res += pathSum(root.right, targetSum);
// 返回当前节点及其子树中满足条件的路径总数
return res;
}
// 计算以某个节点为起点,且路径和等于给定目标值的路径数量
public int rootSum(TreeNode root, int targetSum){
int res = 0;
// 如果当前节点为空,说明已经到达叶子节点的下一层(即不存在),则返回0
if(root == null){
return 0;
}
// 获取当前节点的值
int val = root.val;
// 如果当前节点的值就等于targetSum,说明找到了一条路径(至少是一个节点),增加计数器
if(val == targetSum){
res++;
}
// 递归调用rootSum函数,分别计算左子树和右子树中,以当前节点值为起点,剩余目标值为targetSum-val的路径数量
// 注意:这里是从当前节点开始计算的,所以目标值要减去当前节点的值
res += rootSum(root.left, targetSum - val);
res += rootSum(root.right, targetSum - val);
// 返回以当前节点为起点的所有满足条件的路径数量
return res;
}
看着官解做的,提交不了,类型int不够用,是哪个家伙搞得案例呀,换成long才能通过。
4、复杂度分析
- 时间复杂度: O ( n 2 ) O(n^2) O(n2),n为二叉树节点个数。对于每一个节点,求以该节点为起点的路径数目时,则需要遍历以该节点为根节点的子树的所有节点,因此求该路径所花费的最大时间为
O(N),我们会对每个节点都求一次以该节点为起点的路径数目,因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 - 空间复杂度:O(n),递归需要在栈上开辟空间。
okok,就到这儿吧,拜拜啦!