http://www.lintcode.com/en/problem/binary-tree-path-sum/ https://leetcode.com/problems/path-sum-ii/description/

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

Example

 Given a binary tree, and target = 5:

   1
  / \
 2   4
/ \
   2   3
return

[
  [1, 2, 2],
  [1, 4]
]

解题：题目要求从root到leaf的path sum 等于给定的一个target的值。我们可以每一层用target减去当前值，然后检查看如果target为0并且是leaf，我们就找到了一个解，放入结果。

public class Solution {
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }
        dfs(root, target, new ArrayList<Integer>(), result);
        return result;
    }

    public void dfs(TreeNode root, int target, ArrayList<Integer> subset, List<List<Integer>> result) {
        if(root == null) return;
        subset.add(root.val);
        target = target - root.val;
        if(root.left == null && root.right == null && target == 0){
            result.add(new ArrayList<Integer>(subset));
            subset.remove(subset.size()-1);
            return ;
        }
        if(root.left != null) dfs(root.left, target, subset, result);
        if(root.right!= null) dfs(root.right, target, subset, result);
        subset.remove(subset.size()-1);
    }
}