437. 路径总和 III
2023-04-18 16:13:48 时间
一 题目:
二 思路:
- 递归:每个结点作为开始结点向下寻找和为target的路径
- 注意:
- 1.结点本身可能就值为target
- 2 这里不能过程中返回,因为咱们这个数存在负数,不到null结点都有可能是我们的目标
三 代码:
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root==null){
return 0;
}
int count =dfs(root,targetSum);
int countLeft = pathSum(root.left, targetSum);
int countRight=pathSum(root.right,targetSum);
return count+countLeft+countRight;
}
/**
* 以curr为起点的连续路径是否有结点和为targetSum的数
* count当前起点和为tarsum的值个数
*/
private int dfs(TreeNode root, int targetSum) {
if (root==null){
return 0;
}
targetSum-=root.val;
//当前结点是否已满足条件
int curr=0;
if (targetSum==0){
curr=1;
}
//这里不能加currVal>targetSum或者root.val>targetSum因为咱注意到里面有负数,人家后面还是有希望翻盘的
return curr+dfs(root.left,targetSum)+dfs(root.right,targetSum);
}
}
相关文章
- 第七章 人工智能博弈
- c 语言文件读写
- 中创沙龙预告 | 以ChatGPT的视角探索人工智能的未来
- win11 安卓子系统(WSA)安装教程
- 物联网视频监控服务(三)-监控服务端 篇
- Android 12 Wifi 开发(获取列表、连接、断开连接)
- 分布式事务解决方案---Seata
- Linux基础命令大全(上)
- 设计一个权限系统-RBAC
- Spring Security的使用教程
- 小程序页面间传参的五种方式
- 产品研发项目进度管理软件工具有哪些推荐?整理10款最佳进度管理软件
- 封包协议,加密解密,线程发包,recv,明文收包
- leetcode:有效地括号
- ES: 设置默认值
- Cisco Modeling Labs (CML) 2.5 - 思科建模实验室
- 【Zookeeper 初级】03、Zookeeper 客户端命令行操作
- 算法套路三:二分查找——红蓝染色法
- k8s学习之路 | k8s 工作负载 StatefulSet
- C语言函数:错误信息打印函数,strerror()与perror()