输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

1
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target)

维护一个二维数组，从 root 节点开始进行 dfs。每遍历一个节点， target - 节点值；同时给数组加上该节点。当 target 的值和节点值相等的时候，说明这条路径是合法路径。在二维数组中加上该路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    dfs(root, path, paths, target);
    return paths;
}

private void dfs(TreeNode root, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths, int sum) {
    if (root == null) return;
    path.add(root.val);
    if (root.left == null && root.right == null && sum == root.val) paths.add(new ArrayList<>(path));
    dfs(root.left, path, paths, sum - root.val);
    dfs(root.right, path, paths, sum - root.val);
    path.remove(path.size() - 1);
}