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

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


//寻找最短的 二叉树搜索路径
public class Solution2 {
    private ArrayList<ArrayList<Integer>> allPaths=new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> onePath=new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> findAllPath(TreeNode root) {
        if(root==null)
            return allPaths;
        onePath.add(root.val);
        //若为叶子节点，则onePath加入到allPaths;
        if(root.left==null&&root.right==null){
             allPaths.add(new ArrayList<Integer>(onePath));
        }
        findAllPath(root.left);
        findAllPath(root.right);
        onePath.remove(onePath.size()-1);
        return allPaths;
    }
}

/**

• 剑指Offer面试题34：二叉树中和为某一个值的路径
• 题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
• 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
• 思路：参考剑指Offer
  1、当用前序遍历的方式访问到某一个节点时，我们把该节点添加到路径上，并累加该节点的值。
  2、如果该节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则当前路径符合要求。
  3、如果当前节点不是叶节点，则继续访问它的子节点。
  4、当前节点访问结束后，递归函数将自动回到它的父节点。所以，在函数退出之前要在路径上删除当前节点并减去当前节点的值，
  确保返回父节点时路径刚好是从根节点到父节点。
  */

public class Solution {
    //记录所有的路径
    private ArrayList<ArrayList<Integer>> listAll=new ArrayList<ArrayList<Integer>>();
    //记录一条
    private ArrayList<Integer> listOne=new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target) {
        if(root==null)
            return listAll;
        listOne.add(root.val);
        target-=root.val;
        if(target==0&&root.left==null&&root.right==null)
            listAll.add(new ArrayList<Integer>(listOne));
        findPath(root.left,target);
        findPath(root.right,target);
        listOne.remove(listOne.size()-1);
        return listAll;
    }
}