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);
        //若為葉子節(jié)點(diǎn)，則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：二叉樹中和為某一個(gè)值的路徑
• 題目：輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。
• 路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。
• 思路：參考劍指Offer
  1、當(dāng)用前序遍歷的方式訪問到某一個(gè)節(jié)點(diǎn)時(shí)，我們把該節(jié)點(diǎn)添加到路徑上，并累加該節(jié)點(diǎn)的值。
  2、如果該節(jié)點(diǎn)為葉節(jié)點(diǎn)，并且路徑中節(jié)點(diǎn)值的和剛好等于輸入的整數(shù)，則當(dāng)前路徑符合要求。
  3、如果當(dāng)前節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則繼續(xù)訪問它的子節(jié)點(diǎn)。
  4、當(dāng)前節(jié)點(diǎn)訪問結(jié)束后，遞歸函數(shù)將自動(dòng)回到它的父節(jié)點(diǎn)。所以，在函數(shù)退出之前要在路徑上刪除當(dāng)前節(jié)點(diǎn)并減去當(dāng)前節(jié)點(diǎn)的值，
  確保返回父節(jié)點(diǎn)時(shí)路徑剛好是從根節(jié)點(diǎn)到父節(jié)點(diǎn)。
  */

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;
    }
}