剑指offer二十四之二叉树中和为某一值的路径

import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
        if (root == null) return paths;
        find(paths, new ArrayList<Integer>(), root, target);
        return paths;
    }

    public void find(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, TreeNode root, int target) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            if (target == root.val) {
                paths.add(path);
            }
            return;
        }

        //存储右节点的路径
        ArrayList<Integer> path2 = new ArrayList<>();
        path2.addAll(path);

        if (root.left != null) find(paths, path, root.left, target - root.val);
        if (root.right != null) find(paths, path2, root.right, target - root.val);
    }
}

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

import java.util.ArrayList;

public class TestMain {
    public static void main(String[] args) {
        //建立二叉树，注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
        TreeNode G = new TreeNode(3, null, null);
        TreeNode F = new TreeNode(6, null, null);
        TreeNode E = new TreeNode(5, null, null);
        TreeNode D = new TreeNode(4, null, null);
        TreeNode C = new TreeNode(3, F, G);
        TreeNode B = new TreeNode(2, D, E);
        TreeNode A = new TreeNode(1, B, C);

        //调用方法
        Solution solution = new Solution();
        ArrayList<ArrayList<Integer>> paths = solution.FindPath(A,7);

        /*输出所有路径  
            1 2 4
            1 3 3   
        */
        for (ArrayList<Integer> s : paths) {
            for (int i = 0; i < s.size(); i++) {
                System.out.print(s.get(i) + " ");
            }
            System.out.println();   
        }
    }
}