题目

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 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); //回溯
    }