题目：
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[ [5,4,11,2], [5,8,4,5] ]
思路：
注意必须到 leaf node
package tree; import java.util.ArrayList; import java.util.List; public class PathSumII { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) return res; List<Integer> record = new ArrayList<Integer>(); pathSum(res, record, root, sum); return res; } private void pathSum(List<List<Integer>> res, List<Integer> record, TreeNode root, int sum) { if (root == null && sum != 0) return; if (root == null && sum == 0) { res.add(record); } else { if (root.left == null || root.right == null) { List<Integer> newRecord = new ArrayList<Integer>(record); newRecord.add(root.val); pathSum(res, newRecord, root.left == null ? root.right : root.left, sum - root.val); } else { List<Integer> newRecord1 = new ArrayList<Integer>(record); newRecord1.add(root.val); pathSum(res, newRecord1, root.left, sum - root.val); List<Integer> newRecord2 = new ArrayList<Integer>(record); newRecord2.add(root.val); pathSum(res, newRecord2, root.right, sum - root.val); } } } }