easy级别，再把题目梳理一下
437. Path Sum IIIEasy
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.
树最多有1000个节点。值得范围从-1000000到1000000
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.
返回3，因为有三条这样得路径
The paths that sum to 8
are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
我写了一个算法。先遍历从根节点到叶子的所有路径 这个例子中就四条。放在一个list中 然后一个个拿出来 看有没有从前到后顺序加等于 sum的 结果算重复了 因为5->3 有两条路径都包括。哇顿时觉得有必要和大家分享一下。看看是不是在遍历的时候就加好呢？
会重复计算的代码。C#写呃
private List<List<int>> paths = new List<List<int>>();
public int PathSum(TreeNode root, int sum)
{
int combines = 0;
WalkTree(root, new List<int>());
foreach (List<int> path in paths)
{
for (int i = 0; i < path.Count; i++)
{
int adds = path[i];
for (int j = i + 1; j < path.Count; j++)
{
adds += path[j];
if (adds == sum) combines++;
}
}
}
return combines;
}
private void WalkTree(TreeNode root, List<int> history)
{
if (root != null)
{
history.Add(root.val);
if (root.left == null && root.right == null)
{
paths.Add(history);
}
else
{
List<int> historycopy = new List<int>(history);
WalkTree(root.left, history);
WalkTree(root.right, historycopy);
}
}
}

感觉不是easy，我又写了一次，第一遍递归写错了。
其实递归的思路很清晰，不需要额外空间。
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root==null) return 0;
return dfs(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum);
}
// dfs record the number of path sum must include root
private int dfs(TreeNode root, int sum) {
if(root==null) return 0;
int count=0;
if(root.val==sum) count=1;
return count+dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val);
}
}

大佬带带我

俺也一样

我果然是全吧最菜的