题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
相关话题：树、深度优先搜索 难度：中等
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
返回:
[
[5,4,11,2],
[5,8,4,5]
]
思路：这道题和112题很像，唯一不同是它需要把路径保存下来。
那么我们就需要想办法把遍历过的路径保存下来。
- 如果当前节点是null，直接return，否则加到list。
- 如果当前节点是叶子节点，并且sum已经累加到了目标和，说明这条路径是满足条件的，将list加入到路径容器res中。
注意：不能res.add(list)，res保存的是list的引用，下次list内容修改了，res所保存的值也会修改了，因此我们要保存一个新的list对象，res.add(new ArrayList(list)) -
不满足第二点的话，就递归遍历左子树和右子树，左右子树遍历完，返回前一个节点需要将list的最后一个值删掉。
如上图遍历到节点7，节点7的左右子树都是空，程序会返回节点11再遍历节点2，那么需要将list中的最后一个元素删掉。(返回上一级的时候删除)
- 代码
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
pathSum(root,sum,res,list);
return res;
}
public void pathSum(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list){
if(root == null) return;
list.add(root.val);
if(root.left == null && root.right == null && sum == root.val){
res.add(new ArrayList(list));
}
pathSum(root.left,sum-root.val, res, list);
pathSum(root.right,sum-root.val, res, list);
list.remove(list.size()-1);
}
