一筋栋、題目
給定一個(gè)二叉樹的根節(jié)點(diǎn) root 炊汤，和一個(gè)整數(shù) targetSum ，求該二叉樹里節(jié)點(diǎn)值之和等于 targetSum 的 路徑 的數(shù)目弊攘。
路徑 不需要從根節(jié)點(diǎn)開始抢腐，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）襟交。
二迈倍、示例
2.1> 示例 1：
【輸入】root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
【輸出】3
【解釋】和等于 8 的路徑有 3 條，如圖所示婿着。
2.2> 示例 2：
【輸入】root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
【輸出】3
提示:
- 二叉樹的節(jié)點(diǎn)個(gè)數(shù)的范圍是
[0,1000] -
-10^9<= Node.val <=10^9 -
-1000<= targetSum <=1000
三授瘦、解題思路
根據(jù)題意醋界，給出了我們解答此題的一些關(guān)鍵信息：
【信息1】“
徑方向必須是向下”——根據(jù)這條信息竟宋，我們可以確定遍歷操作方向；
【信息2】“路徑不需要從根節(jié)點(diǎn)開始形纺，也不需要在葉子節(jié)點(diǎn)結(jié)束”——可以隨意區(qū)間簡(jiǎn)單構(gòu)成路徑丘侠；
根據(jù)以上兩條信息，我們可以首先先到采用前綴和的方式進(jìn)行解題逐样，因?yàn)榍熬Y和適合解答那種連續(xù)蜗字、累積和這類題目。那么什么是前綴和呢脂新？我們可以以下圖為例挪捕，如果有4個(gè)節(jié)點(diǎn)，分別是10争便、5级零、2、1滞乙，它的前綴和就分別是10奏纪、15鉴嗤、17和18；
那么我們可以通過(guò)前綴和的值來(lái)計(jì)算任意連續(xù)的節(jié)點(diǎn)和序调，比如：
【求節(jié)點(diǎn)5到節(jié)點(diǎn)2之和】可以用
前綴和17-前綴和10醉锅，那么結(jié)果就是5；
【求節(jié)點(diǎn)5到節(jié)點(diǎn)1之和】可以用前綴和18-前綴和10发绢，那么結(jié)果就是8硬耍；
了解了前綴和之后，我們就可以從樹的root節(jié)點(diǎn)開始遍歷边酒，此處我們可以采用前序遍歷的方式默垄，那么還有兩個(gè)細(xì)節(jié)問(wèn)題需要解決：
問(wèn)題1：采用什么數(shù)據(jù)結(jié)構(gòu)來(lái)保存前綴和？
我們可以通過(guò)創(chuàng)建Map結(jié)構(gòu)甚纲，
key=前綴和口锭，value=相同前綴和值的數(shù)量；
問(wèn)題2：采用前序遍歷計(jì)算樹節(jié)點(diǎn)的前綴和介杆，難免會(huì)出現(xiàn)重復(fù)節(jié)點(diǎn)計(jì)算的情況鹃操，這個(gè)怎么辦？
可以通過(guò)回溯的方式春哨，將值還原到上一步荆隘，避免重復(fù)計(jì)算。
解題思路就這些了赴背，大家采用：前序遍歷+前綴和+回溯這3個(gè)思路結(jié)合方式解題即可椰拒。具體實(shí)現(xiàn)，請(qǐng)見(jiàn)下面代碼實(shí)現(xiàn)部分凰荚。
四燃观、代碼實(shí)現(xiàn)
class Solution {
private Map<Long, Integer> map;
private int result = 0, target = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
target = targetSum;
map = new HashMap();
map.put(0L, 1);
dfs(root, root.val);
return result;
}
public void dfs(TreeNode node, long value) {
result += map.getOrDefault(value - target, 0);
map.put(value, map.getOrDefault(value, 0) + 1);
if (node.left != null) dfs(node.left, value + node.left.val);
if (node.right != null) dfs(node.right, value + node.right.val);
map.put(value, map.getOrDefault(value, 0) - 1);
}
}
今天的文章內(nèi)容就這些了：
寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章便瑟，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 缆毁。
更多技術(shù)干貨，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(o)/ ~ 「干貨分享到涂，每天更新」
