题目
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
解析
1.递归遍历
2.直叶子节点，判断sum是否和路径和相等
public IList<IList<int>> PathSum(TreeNode root, int sum) {
IList<IList<int>> resPeth = new List<IList<int>>();
IList<int> path = new List<int>();
int pathValue = 0;
Preoder(root, pathValue, sum, path, resPeth);
return resPeth;
}
void Preoder(TreeNode node, int pathValue, int sum, IList<int> path, IList<IList<int>> resPeth)
{
if(node == null) return;
pathValue += node.val;
path.Add(node.val);
if (pathValue == sum&&node.left == null&&node.right == null)
{
resPeth.Add(new List<int>(path));
}
Preoder(node.left, pathValue, sum, path, resPeth);
Preoder(node.right, pathValue, sum, path, resPeth);
pathValue -= node.val;
if(path.Count>0)
path.RemoveAt(path.Count-1); //回溯
}
