【剑指Offer】二叉树中和为某一值的路径

题目链接

题目描述

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

解题思路：

• 使用DFS进行遍历，如果符合，就添加到list集合中
• 在退出当前层时，要将添加的数移除掉

代码：

/**
 * @author: hyl
 * @date: 2019/08/15
 **/
public class Que24 {

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

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

        }

    }

    private ArrayList<ArrayList<Integer>> resAll = new ArrayList<>();
    private ArrayList<Integer> list = new ArrayList<>();

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


        if (root == null){
            return resAll;
        }

        list.add(root.val);
        target -= root.val;

        if (target == 0 && root.left == null && root.right == null){
            resAll.add(list);
        }

        FindPath(root.left , target);
        FindPath(root.right , target);

        list.remove(list.size() - 1);


        return resAll;

        
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(5);

        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(3);

        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(1);

        new Que24().FindPath(root,11);
    }
}

代码地址：
https://github.com/Han-YLun/jianzhiOffer/blob/master/Solution/src/Que24.java

文章为阿伦原创,如果文章有错的地方欢迎指正，大家互相交流。