9.path Sum III(路径和 III)
2024-08-29 03:57:02
Level:
Easy
题目描述:
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
思路分析:
由于题目中所说的路径,不局限于从根到叶子节点,任何一个节点都可以作为路径的开始节点和终止节点,所以我们以根节点作为开始节点,查找和为sum的路径数,然后分别以根的左孩子和右孩子为起始节点去查找和为sum的路径数,依次递归向下推导,得到最终的结果。
代码:
/**public class TreeNode{
int vla;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val=val;
}
}*/
public class Soulution{
public int pathSum(TreeNode root,int sum){
if(root==null)
return 0;
int res=0;
res=pathCheck(root,sum);
res=res+pathSum(root.left,sum);
res=res+pathSum(root.right,sum);
return res;
}
public int pathCheck(TreeNode root,int sum){
if(root==null)
return 0;
int count=0;
if(sum==root.val)//当sum等于root.val时证明存在一条路径和为sum
count++;
count=count+pathCheck(root.left,sum-root.val);
count=count+pathCheck(root.right,sum-root.val);
return count;
}
}
最新文章
- Linux安装xwindow图形界面(转载)
- Bubble Cup 8 finals E. Spectator Riots (575E)
- SVEditor 1.3.6 发布
- TC79
- Python入门-多行语句
- 爱拼图游戏android源码完整版
- 通过keepalived实现 MySQL VIP 自动切换
- hdu2795--Billboard
- Git学习04 --分支管理
- Google Maps API V2
- 参照openRTSP写的一个RTSP client 加了一些注解
- db_link
- SSM-SpringMVC-30:SpringMVC中InitBinder的骇客级优化
- [MicroPython]TPYBoardv102超全DIY案例一览
- Nginx 决策浏览器缓存是否有效
- python,异常处理
- 转一篇 ShaderVariantCollection介绍的比较详细的文章 感谢作者
- 批处理FINDSTR正则表达式用法实例分析
- [技术] OIer的C++标准库 : STL入门
- ERP渠道活动管理(二十六)