LeetCode -- Path Sum III分析及实现方法
作者:lqh 时间:2022-10-16 13:41:14
LeetCode -- Path Sum III分析及实现方法
题目描述:
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.
给定一个二叉树,遍历过程中收集所有可能路径的和,找出和等于X的路径树。
思路:
设当前节点为root,分别收集左右节点路径和的集合,merge到当前集合中;
将当前节点添加到数组中,构成新的可能路径。
实现代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int _sum;
private int _count;
public int PathSum(TreeNode root, int sum)
{
_count = 0;
_sum = sum;
Travel(root, new List<int>());
return _count;
}
private void Travel(TreeNode current, List<int> ret){
if(current == null){
return ;
}
if(current.val == _sum){
_count ++;
}
var left = new List<int>();
Travel(current.left, left);
var right = new List<int>();
Travel(current.right, right);
ret.AddRange(left);
ret.AddRange(right);
for(var i = 0;i < ret.Count; i++){
ret[i] += current.val;
if(ret[i] == _sum){
_count ++;
}
}
ret.Add(current.val);
//Console.WriteLine(ret);
}
}
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/lan_liang/article/details/55826872
标签:LeetCode,Path,Sum
0
投稿
猜你喜欢
Java中Lombok常用注解分享
2023-06-13 01:32:48
IDEA中java断言assert语法及使用
2022-12-28 21:07:00
vista和win7在windows服务中交互桌面权限问题解决方法:穿透Session 0 隔离
2021-06-16 04:05:47
Android自定义ProgressDialog加载图片
2022-07-28 22:08:39
从汇编码分析java对象的创建过程(推荐)
2023-06-09 18:05:17
Android webView加载数据时内存溢出问题及解决
2021-06-24 13:19:28
C#无损压缩图片
2022-05-26 22:54:39
深度剖析java动态静态代理原理源码
2021-10-25 08:10:31
事务在c#中的使用
2021-11-27 23:30:29
Java循环结构之多重循环及continue break
2023-11-10 15:39:14
Android12四大组件之Activity生命周期变化详解
2022-05-04 15:47:57
Java ConcurrentHashMap的源码分析详解
2023-05-02 02:16:21
Android应用内悬浮窗Activity的简单实现
2023-07-28 04:03:00
C#简单的加密类实例
2022-12-15 11:31:18
C#使用后台线程BackgroundWorker处理任务的总结
2023-12-08 10:28:19
spring boot微服务场景下apollo加载过程解析
2022-05-20 13:55:32
java实现压缩字符串和java字符串过滤
2023-01-06 10:35:19
springboot aop里的@Pointcut()的配置方式
2021-11-18 20:55:37
解析spring事务管理@Transactional为什么要添加rollbackFor=Exception.class
2021-09-03 17:07:41
java ReentrantLock条件锁实现原理示例详解
2023-12-12 02:36:13