输出和为指定值的路径

 1 import java.util.ArrayList;
 2 
 3 public class PrintPathWithSum {
 4     ArrayList<ArrayList<Integer>> res = new ArrayList<>();
 5 
 6     public ArrayList<ArrayList<Integer>> FindPath(TreeNode<Integer> root, int target) {
 7         if (root == null)
 8             return res;
 9         f(new ArrayList<Integer>(), root, target);
10         res.sort((l1, l2) -> {
11             return -l1.size() + l2.size();
12         });
13         return res;
14     }
15 
16     void f(ArrayList<Integer> pre, TreeNode<Integer> node, int target) {
17         ArrayList<Integer> _pre = new ArrayList<>();
18         _pre.addAll(pre);
19         _pre.add(node.val);
20 
21         if (node.left == null && node.right == null) {
22             if (target - node.val == 0) {
23                 res.add(_pre);
24             }
25             return;
26         }
27 
28         if (node.left != null)
29             f(_pre, node.left, target - node.val);
30         if (node.right != null) {
31             f(_pre, node.right, target - node.val);
32         }
33     }
34 
35     public static void main(String[] args) {
36         PrintPathWithSum obj = new PrintPathWithSum();
37         TreeNode<Integer> root = new TreeNode<>(1);
38         TreeNode<Integer> l = new TreeNode<>(2);
39         TreeNode<Integer> r = new TreeNode<>(3);
40         TreeNode<Integer> ll = new TreeNode<>(8);
41         TreeNode<Integer> lr = new TreeNode<>(6);
42         TreeNode<Integer> rl = new TreeNode<>(7);
43         TreeNode<Integer> rr = new TreeNode<>(4);
44         TreeNode<Integer> lrl = new TreeNode<>(2);
45         TreeNode<Integer> rrr = new TreeNode<>(2);
46         TreeNode<Integer> rrrr = new TreeNode<>(1);
47         root.left = l;
48         root.right = r;
49         l.left = ll;
50         l.right = lr;
51         r.right = rr;
52         r.left = rl;
53         lr.left = lrl;
54         rr.right = rrr;
55         rrr.right = rrrr;
56         ArrayList<ArrayList<Integer>> lists = obj.FindPath(root, 11);
57         for (ArrayList<Integer> list : lists) {
58             System.out.println(list);
59         }
60     }
61 
62     public static class TreeNode<T> {
63 
64         public T val;
65         public TreeNode<T> left = null;
66         public TreeNode<T> right = null;
67         public TreeNode<T> parent = null;
68 
69         public TreeNode(T val) {
70             this.val = val;
71         }
72     }
73 }