題目輸入一顆二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。

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

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

    }

}
*/

分析題目：

• 某個路徑上的節(jié)點的和為輸入的數(shù)。
• 看到了路徑，想到了深度優(yōu)先遍歷，這一定是一道深度優(yōu)先遍歷的題。
• 既然是深度優(yōu)先遍歷，那應該使用?；蛘哌f歸。

那么就會產(chǎn)生下面幾個問題：

• 如何存儲路徑上的和的值
• 如果使用遞歸，終止條件的選擇
• 如果發(fā)現(xiàn)一個路徑與符合題意，如果將其放入ArrayList中
• 多個符合條件的路徑公用一些節(jié)點

public class Solution {
    private ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();//存儲結(jié)果
    private ArrayList<Integer> array = new ArrayList<>();//用于存儲當前調(diào)用棧的節(jié)點，遞歸結(jié)束節(jié)點自動刪去。
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return arrayLists;//結(jié)束
        }
        array.add(root.val);//將本節(jié)點的值加入array中
        target -= root.val; //target減去該路徑中每層節(jié)點的值
        if(target == 0 && root.left == null && root.right == null){//符合題意的條件
            arrayLists.add(new ArrayList<>(array));//將該路徑加入到結(jié)果中
        }
        FindPath(root.left, target);//左子節(jié)點遞歸
        FindPath(root.right, target);//右子節(jié)點遞歸
        array.remove(array.size() - 1);//從array中移除本層節(jié)點，保證array中的永遠保存的是執(zhí)行體所在的節(jié)點以上的路徑。保證數(shù)據(jù)清潔，
        return arrayLists;//返回值僅用于最后的返回條件，無時間邏輯意義
    }
}

可以說，這是我刷題以來見過的最棒的一個代碼了，從這里面學了很多知識

• 無用的數(shù)據(jù)及時刪除，可以保證整個數(shù)據(jù)的整潔。
• 當需要記錄很多個array時，可以通過構(gòu)造參數(shù)復制公共array，之后公共array仍可以安全的更新