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

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