LeetCode -- Path Sum III分析及实现方法
更新时间:2017年10月25日 14:32:22 投稿:lqh
这篇文章主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
(福利推荐:【腾讯云】服务器最新限时优惠活动,云服务器1核2G仅99元/年、2核4G仅768元/3年,立即抢购>>>:9i0i.cn/qcloud)
(福利推荐:你还在原价购买阿里云服务器?现在阿里云0.8折限时抢购活动来啦!4核8G企业云服务器仅2998元/3年,立即抢购>>>:9i0i.cn/aliyun)
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); } }
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
JavaWeb项目web.xml中出现Element xxx is not al
这篇文章主要介绍了JavaWeb项目web.xml中出现Element xxx is not allowed here问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教2023-11-11
最新评论