題目
給定一個二叉樹和一個目標和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑漓柑，這條路徑上所有節(jié)點值相加等于目標和。
摘自LeetCode112
解題方法
遞歸實現(xiàn)
目標sum值減去根節(jié)點的關鍵值叨吮，結果分別是根節(jié)點的左右子樹的目標和辆布。對左右子樹遞歸調用函數(shù)，直到樹葉節(jié)點為止茶鉴。
代碼
public boolean hasPathSum(TreeNode root, int sum) {
if(null == root){//根節(jié)點為空锋玲，則返回false
return false;
}
//直到樹葉節(jié)點，如果關鍵值等于遞歸傳入的sum值涵叮，則返回true
if(null == root.left && null == root.right && root.val == sum){
return true;
}
//非樹葉節(jié)點惭蹂，對左右子樹遞歸調用函數(shù)
//目標和要減去當前節(jié)點的關鍵值
boolean l = hasPathSum(root.left, sum - root.val);
boolean r = hasPathSum(root.right, sum - root.val);
return l || r;
}
拓展題目
如果題目要求不是判斷是否存在這條路徑，而是返回滿足條件的路徑割粮？（LeetCode113）
拓展題目解析
- 與上一題思路一樣盾碗，區(qū)別在于遞歸不再返回是否存在路徑，而是需要記錄遍歷過的節(jié)點舀瓢。
- 實現(xiàn)中我們在遞歸函數(shù)中傳入用于存儲遍歷過節(jié)點的隊列結構廷雅。
- 同時，因為遞歸是先遍歷左子樹再遍歷右子樹，只有左子樹遞歸到樹葉節(jié)點之后才會開始遍歷右子樹航缀，那么我們可以僅僅使用同一個隊列進行參數(shù)傳遞商架，在每個節(jié)點的左右子樹遞歸遍歷之后，移除當前的節(jié)點芥玉，這樣可以減少不斷構建新隊列所帶來的性能消耗蛇摸。
拓展題目代碼
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
pathSumHelper(root, sum, result, list);
return result;
}
//遞歸尋找存在的路徑
private void pathSumHelper(TreeNode root, int sum,
List<List<Integer>> result, List<Integer> list){
if(null == root){
return;
}
if(null == root.left && null == root.right && sum == root.val){
//遍歷到樹葉節(jié)點如果符合條件，存入隊列中
list.add(root.val);
//復制一個新的隊列存入結果隊列中
result.add(new ArrayList<Integer>(list));
//移除當前節(jié)點灿巧，其他遍歷分支繼續(xù)使用這個隊列
list.remove(list.size() - 1);
return;
}
//遍歷到非樹葉節(jié)點赶袄，存入隊列中
list.add(root.val);
//遞歸左子樹與右子樹
pathSumHelper(root.left, sum - root.val, result, list);
pathSumHelper(root.right, sum - root.val, result, list);
//移除當前節(jié)點，其他遍歷分支繼續(xù)使用這個隊列
list.remove(list.size() - 1);
}
