題目輸入一顆二叉樹和一個整數(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)先遍歷鸿市，那應(yīng)該使用棧或者遞歸即碗。
那么就會產(chǎn)生下面幾個問題：
- 如何存儲路徑上的和的值
- 如果使用遞歸焰情，終止條件的選擇
- 如果發(fā)現(xiàn)一個路徑與符合題意，如果將其放入ArrayList中
- 多個符合條件的路徑公用一些節(jié)點
public class Solution {
private ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();//存儲結(jié)果
private ArrayList<Integer> array = new ArrayList<>();//用于存儲當(dāng)前調(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中的永遠(yuǎn)保存的是執(zhí)行體所在的節(jié)點以上的路徑蕊肥。保證數(shù)據(jù)清潔谒获，
return arrayLists;//返回值僅用于最后的返回條件，無時間邏輯意義
}
}
可以說壁却，這是我刷題以來見過的最棒的一個代碼了批狱，從這里面學(xué)了很多知識
- 無用的數(shù)據(jù)及時刪除，可以保證整個數(shù)據(jù)的整潔展东。
- 當(dāng)需要記錄很多個array時赔硫，可以通過構(gòu)造參數(shù)復(fù)制公共array，之后公共array仍可以安全的更新
