///路徑總和I
/*
1.確定遞歸函數(shù)的參數(shù)和返回類型
參數(shù)：需要二叉樹的根節(jié)點(diǎn)，還需要一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器用來計(jì)算二叉樹的一條邊之和是否正好是目標(biāo)和，計(jì)數(shù)器為int型。
*/
private boolean traversal(TreeNode root, int count){
????if (root ==null){
????????return false;
? ? }
? ? /*
? ? 2.確定終止條件
????首先計(jì)數(shù)器如何統(tǒng)計(jì)這一條路徑的和呢？
????不要去累加然后判斷是否等于目標(biāo)和，那么代碼比較麻煩，可以用遞減，讓計(jì)數(shù)器count初始為目標(biāo)和，然后每次減去遍歷路徑節(jié)點(diǎn)上的數(shù)值。
????如果最后count == 0，同時(shí)到了葉子節(jié)點(diǎn)的話，說明找到了目標(biāo)和。
????如果遍歷到了葉子節(jié)點(diǎn)，count不為0，就是沒找到。
????*/
? ? if (root.left ==null && root.right ==null && count ==0){
????????return true;
? ? }
????if (root.left ==null && root.right ==null ){
????????return false;
? ? }
? ? /*
? ? 3.確定單層遞歸的邏輯
????因?yàn)榻K止條件是判斷葉子節(jié)點(diǎn)，所以遞歸的過程中就不要讓空節(jié)點(diǎn)進(jìn)入遞歸了。
? ? 如果未找到滿足條件的，記得回溯
? ? */
????if (root.left){
????????count -= root.left.val;
? ? ? ? traversal(root.left, count); //遞歸
? ? ? ? count += root.left.val; //不滿足條件，回溯
? ? }
????if (root.right){
????????count -= root.right.val;? ? //
? ? ? ? traversal(root.right, count); //遞歸
? ? ? ? count += root.right.val;? ? //不滿足條件，回溯
? ? }
????return false
}
/// 路徑總和II
public List> pathsumII(TreeNode root, int count){
????List> res =new ArrayList<>();
? ? if (root ==null) {
????????return res;
? ? }
????List path =new ArrayList<>();
? ? traversalII(root, count, res, path);
? ? return res;
}
private void traversalII(TreeNode root, int count, List> result, List path){
????path.add(root.val);
? ? if (root.left ==null && root.right ==null && count ==0){
????????result.add(path);
????????return;
? ? }
????if (root.left){
????????count -= root.left.val; //count減去當(dāng)前節(jié)點(diǎn)值
? ? ? ? path.add(root.left.val);? ? //添加當(dāng)前值
? ? ? ? traversal(root.left, count);? ? //遞歸
? ? ? ? count += root.left.val; //回溯
? ? ? ? path.remove(path.size()-1);
? ? }
????if (root.right){
????????count -= root.right.val;? ? //count進(jìn)去當(dāng)前節(jié)點(diǎn)值
? ? ? ? path.add(root.right.val);? //添加當(dāng)前值
? ? ? ? traversalII(root.right, count); //遞歸
? ? ? ? count += root.right.val;? ? //回溯
? ? ? ? path.remove(path.size()-1);
? ? }
}
