?437.路徑總和 III
給定一個二叉樹漓库，它的每個結(jié)點(diǎn)都存放著一個整數(shù)值吧黄。
找出路徑和等于給定數(shù)值的路徑總數(shù)柬帕。
路徑不需要從根節(jié)點(diǎn)開始，也不需要在葉子節(jié)點(diǎn)結(jié)束铅搓，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）瑟押。
二叉樹不超過1000個節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)狸吞。
Solution:
首先我們從根節(jié)點(diǎn)出發(fā)勉耀，去遍歷這個根節(jié)點(diǎn)下所有滿足條件的路徑數(shù)目，每次到達(dá)一個節(jié)點(diǎn)蹋偏，將傳入的參數(shù)sum減去root的val,這是一個遞歸便斥。然后我們需要遍歷所有的根節(jié)點(diǎn)，那么又需要一個遞歸去遍歷威始。兩層遞歸枢纠。
/**
* Definition for a binary tree node.
* public class TreeNode {
*? ? int val;
*? ? TreeNode left;
*? ? TreeNode right;
*? ? TreeNode(int x) { val = x; }
* }
*/
class Solution {
? ? private int count = 0;
? ? public int pathSum(TreeNode root, int sum) {
? ? ? ? if(root==null) return 0;
? ? ? ? path(root,sum);
? ? ? ? pathSum(root.left,sum);
? ? ? ? pathSum(root.right,sum);
? ? ? ? return count;
? ? }
? ? public void path(TreeNode root,int sum){
? ? ? ? if(root==null) return;
? ? ? ? sum = sum-root.val;
? ? ? ? if(sum==0) count++;
? ? ? ? path(root.left,sum);
? ? ? ? path(root.right,sum);
? ? }
}
113.?路徑總和 II
給定一個二叉樹和一個目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑黎棠。
說明:葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)晋渺。
示例:
給定如下二叉樹，以及目標(biāo)和sum = 22脓斩，
有了上題的基礎(chǔ)木西，這題就不難了，還是一樣的思路随静，不同的是不需要遍歷所有的根節(jié)點(diǎn)八千，而且需要我們遍歷到葉子節(jié)點(diǎn)，處理方式就簡單很多燎猛。
/** * Definition for a binary tree node. *?
public class TreeNode { int val; TreeNode left;? TreeNode right; TreeNode(int x) { val = x; }? }?
*/
class Solution {
?List <List<Integer>> list = new ArrayList<>();?
?public List?<List<Integer>> pathSum(TreeNode root, int sum) {?
?????if(root==null) return list;?
?????Listsublist = new ArrayList<>();?
?????path(root,sum,sublist);?
?????return list;
?}?
?public void path(TreeNode root,int sum,List<Integer> sublist){
?????if(root==null){ return; }?
?????List asList = new ArrayList(sublist);
? ? ?sum = sum - root.val;
? ? ?asList.add(root.val);
? ? ?if(sum==0&&root.left==null&&root.right==null){
? ? ? ? ? ? list.add(new ArrayList(asList));return;
? ? ?}
? ? ?path(root.left,sum,asList);
? ? ?path(root.right,sum,asList);? ? ?
? ? }
}
