LeetCode -- Path Sum III分析及实现方法

LeetCode -- Path Sum III分析及实现方法
题目描绘：

1. You are given a binary tree in which each node contains an integer value.
3. Find the number of paths that sum to a given value.
5. 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).
7. 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到当前集合中；

将当前节点添加到数组中，构成新的可能途径。
实现代码：

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. * public int val;
5. * public TreeNode left;
6. * public TreeNode right;
7. * public TreeNode(int x) { val = x; }
8. * }
9. */
10. public class Solution {
12. private int _sum;
13. private int _count;
14. public int PathSum(TreeNode root, int sum)
15. {
16. _count = 0;
17. _sum = sum;
18. Travel(root, new List<int>());
19. return _count;
20. }
22. private void Travel(TreeNode current, List<int> ret){
23. if(current == null){
24.   return ;
25. }
27. if(current.val == _sum){
28.   _count ++;
29. }
31. var left = new List<int>();
32. Travel(current.left, left);
34. var right = new List<int>();
35. Travel(current.right, right);
37. ret.AddRange(left);
38. ret.AddRange(right);
40. for(var i = 0;i < ret.Count; i++){
41.   ret[i] += current.val;
42.   if(ret[i] == _sum){
43.   _count ++;
44.   }
45. }
46. ret.Add(current.val);
48. //Console.WriteLine(ret);
49. }
50. }

复制代码

如有疑问请留言或者到本站社区交流讨论，感激阅读，希望能协助到大家，谢谢大家对本站的支持！