題目
給你二叉樹的根節(jié)點(diǎn)?root?和一個(gè)整數(shù)目標(biāo)和?targetSum?，找出所有?從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)?路徑總和等于給定目標(biāo)和的路徑。
葉子節(jié)點(diǎn)?是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例 1：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]
示例 2：
輸入：root = [1,2,3], targetSum = 5
輸出：[]
示例 3：
輸入：root = [1,2], targetSum = 0
輸出：[]
提示：
- 樹中節(jié)點(diǎn)總數(shù)在范圍?
[0, 5000]?內(nèi) -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解題思路
1.題目要求我們找出所有?從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)?路徑總和等于給定目標(biāo)和的路徑。我們可以使用深度優(yōu)先遍歷來解決這個(gè)問題。
2.舉個(gè)例子：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
首先我們建立兩個(gè)動(dòng)態(tài)數(shù)組res和temp來存儲(chǔ)結(jié)果和遍歷的路徑。
?然后我們從根節(jié)點(diǎn)開始遍歷，先將 5 放入數(shù)組 temp ，并且給 target 減 5 。
此時(shí) target 不為 0 ，那么我們需要繼續(xù)遍歷，再將 5 的左孩子 4 放入temp 中，并且給 target 減 4。
?此時(shí) target 不為 0 ，那么我們需要繼續(xù)遍歷，再將 4?的左孩子 11?放入temp 中，并且給 target 減 11。
??此時(shí) target 不為 0 ，那么我們需要繼續(xù)遍歷，再將 11?的左孩子 7?放入temp 中，并且給 target 減 11。
這時(shí)我們發(fā)現(xiàn) 7 已經(jīng)是葉子節(jié)點(diǎn)，但是target還是不為 0 ，那就說明這條路不是路徑總和等于給定目標(biāo)和的路徑，我們就需要回溯，我們返回上一個(gè)節(jié)點(diǎn)，也就是11。
然后我們?nèi)ケ闅v 11 的右孩子 2 ，?將 11?的右孩子 2 放入temp 中，并且給 target 減 2。
?
此時(shí) target 剛好為 0 ，并且 2 也是葉子節(jié)點(diǎn)，那就說明我們找到了路徑總和等于給定目標(biāo)和的路徑，我們需要將 temp 中保存的路徑放入數(shù)組 res 中，
然后再進(jìn)行回溯按照相同的思路去遍歷其他的節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都遍歷結(jié)束，最后返回 res即可。
代碼實(shí)現(xiàn)
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public List<List<Integer>> pathSum(TreeNode root, int target) {
res = new ArrayList<>();
temp = new ArrayList<>();
dsf(root,target);
return res;
}
void dsf(TreeNode root, int target){
if(root == null){
return;
}
temp.add(root.val);
target = target - root.val;
if(root.left == null && root.right == null && target == 0){
res.add(new ArrayList(temp));
}
dsf(root.left, target);
dsf(root.right, target);
temp.remove(temp.size()-1);
}
}測(cè)試結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-667439.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-667439.html
到了這里，關(guān)于Leetcode-每日一題【劍指 Offer 34. 二叉樹中和為某一值的路徑】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
