題目描述
輸入一顆二叉樹和一個(gè)整數(shù)聪轿，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑背捌。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑典阵。
代碼實(shí)現(xiàn)
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<Integer> path = new ArrayList<>();
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null)
return list;
//每訪問到一個(gè)結(jié)點(diǎn)的時(shí)候疾宏，都把當(dāng)前的結(jié)點(diǎn)添加到路徑中去后添，并調(diào)整target的值
path.add(root.val);
target -= root.val;
//已到葉節(jié)點(diǎn)并且和為target黍特，則把當(dāng)前路徑添加到輸出列表里
//因?yàn)閍dd添加的是引用蛙讥，如果不new一個(gè)的話，最終list保存到的只是最后一個(gè)path
if(target == 0 && root.left == null && root.right == null)
list.add(new ArrayList<Integer>(path));
//否則繼續(xù)遍歷
FindPath(root.left, target);
FindPath(root.right, target);
//已到葉節(jié)點(diǎn)之后會(huì)跳過兩個(gè)遞歸函數(shù)到這里灭衷，此時(shí)要把最后一個(gè)結(jié)點(diǎn)從路徑中刪除次慢，才能返回上層結(jié)點(diǎn)
path.remove(path.size()-1);
return list;
}
}
主要思路
1、這道題有點(diǎn)難度翔曲，首先記住一句話：在樹的前序迫像、中序、后序遍歷中瞳遍，只有前序遍歷是首先遍歷根結(jié)點(diǎn)的（因此需要先遍歷根結(jié)點(diǎn)的題闻妓，就是考查前序遍歷）
2、代碼注釋里寫的比較清楚了掠械，首先就是要把當(dāng)前結(jié)點(diǎn)（首先是根結(jié)點(diǎn)）添加到路徑里由缆，同時(shí)target 減去當(dāng)前結(jié)點(diǎn)的值；然后猾蒂，如果當(dāng)前結(jié)點(diǎn)為葉節(jié)點(diǎn)并且和也達(dá)到給定值均唉，就把這個(gè)路徑添加到列表，否則就一直遍歷下去肚菠；最后舔箭，遍歷到葉節(jié)點(diǎn)之后，返回上層結(jié)點(diǎn)之前案糙，一定要把最后一個(gè)結(jié)點(diǎn)從路徑中刪除
3限嫌、把符合條件的路徑添加到列表中的時(shí)候，因?yàn)閍dd添加的是引用时捌，如果不是每次都new一個(gè)path的話怒医，最終list保存到的只是最后一個(gè)path（可以看一下ArrayList的源碼）
