437. 路徑總和 III
給定一個二叉樹耸棒，它的每個結(jié)點都存放著一個整數(shù)值。
找出路徑和等于給定數(shù)值的路徑總數(shù)报辱。
路徑不需要從根節(jié)點開始与殃，也不需要在葉子節(jié)點結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）碍现。
二叉樹不超過1000個節(jié)點幅疼，且節(jié)點數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3昼接。和等于 8 的路徑有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
雙重遞歸
/*
思路：
1.dfs是求從根節(jié)點出發(fā)到葉子節(jié)點滿足條件的路徑總數(shù)
2.將給定的二叉樹看成三個部分：根節(jié)點爽篷、左子樹、右子樹
3.三部分可以看成一個遞歸結(jié)構(gòu)慢睡，先求從根節(jié)點出發(fā)滿足條件的路徑總數(shù)(dfs(root))逐工，
再遞歸求左子樹(pathSum(root.left))铡溪，遞歸求右子樹(pathSum(root.right))
總結(jié)：
1.雙重遞歸，從全局找外層遞歸(如思路中的三個部分)泪喊，再從部分中找內(nèi)層遞歸(如思路中的dfs)
*/
class Solution {
private int count = 0; //存放結(jié)果
public int pathSum(TreeNode root, int sum) {
if(root == null) return 0;
dfs(root, sum); //求從根節(jié)點出發(fā)滿足條件的路徑總數(shù)
pathSum(root.left, sum); //遞歸求左子樹
pathSum(root.right, sum); //遞歸求右子樹
return count;
}
private void dfs(TreeNode root, int sum){
if(root == null) return;
sum -= root.val;
if(sum == 0) count++; //滿足條件結(jié)果加一
dfs(root.left, sum); //繼續(xù)往左子樹找
dfs(root.right, sum); //繼續(xù)往右子樹找
}
}
單重遞歸
/*
思路：
1.用雙重遞歸會重復計算很多次棕硫，其實我們只用單遞歸就可以解決，
不妨將已經(jīng)走過的路徑值保存到book數(shù)組
2.到i節(jié)點窘俺，就可以根據(jù)book倒序遍歷饲帅，找到從i節(jié)點到根節(jié)點滿足條件的路徑總數(shù)
3.遞歸到最底層也就是葉子節(jié)點時，找出葉子節(jié)點到根節(jié)點的滿足條件的路徑總數(shù)之后瘤泪，
需要將book數(shù)組回溯到上一層的狀態(tài)灶泵，以便從上一層繼續(xù)尋找
總結(jié)：
1.將已經(jīng)求出的值保存，當下次遞歸時可以直接使用对途，
省去了重復計算浪費的時間赦邻，相當于用空間換取時間
2.遞歸返回到上層時，我們有時需要原來上層遞歸的狀態(tài)实檀，這時就需要用到回溯
*/
class Solution {
private int count = 0; //存放結(jié)果
public int pathSum(TreeNode root, int sum) {
dfs(root, sum, new ArrayList<Integer>());
return count;
}
private void dfs(TreeNode root, int sum, ArrayList<Integer> book){
if(root == null) return;
book.add(root.val); //加入當前節(jié)點的值
int cur_sum = 0;
for(int i = book.size() - 1; i >= 0; i--){ //從當前節(jié)點往根節(jié)點尋找滿足條件的路徑總數(shù)
cur_sum += book.get(i);
if(cur_sum == sum) count++;
}
dfs(root.left, sum, book); //遞歸求左子樹
dfs(root.right, sum, book); //遞歸求右子樹
book.remove(book.size() - 1); //回溯到上一次的狀態(tài)惶洲，以便繼續(xù)尋找
}
}
