leetcode 437
思路
利用前綴和+hash map解答
前綴和在這里的含義是：從根節點到當前節點的路徑上所有節點值的總和
我們使用一個 Map 數據結構來記錄這些前綴和及其出現的次數
具體思路如下：
- 初始化：創建一個
Map，并將前綴和0出現的次數初始化為1。這是因為在遍歷開始時，我們還沒有訪問任何節點，此時的前綴和就是0，它的出現次數為1次。同時，初始化一個變量count用于記錄滿足條件的路徑數量，初始值為0
const map = new Map();?
map.set(0, 1);?
let count = 0;
- 深度優先搜索：定義一個遞歸函數
deep用于進行深度優先遍歷。在每次遞歸中，我們計算當前節點的前綴和curSum，它等于從根節點到上一個節點的前綴和sum加上當前節點的值root.val
const deep = (root, sum) => {?
if (!root) return;?
const curSum = sum + root.val;
- 判斷是否存在滿足條件的路徑：計算當前前綴和
curSum與目標值targetSum的差值diff，即diff = curSum - targetSum。如果 Map 中存在 diff 這個前綴和，說明從根節點到當前節點的路徑中，存在一段子路徑的和等于目標值targetSum，那么滿足條件的路徑數量就需要加上diff出現的次數
const diff = curSum - targetSum?
if (map.has(diff)) {?count += map.get(diff);?
}
- 更新前綴和及其出現次數：如果
Map中已經存在當前前綴和curSum，則將其出現次數加1；否則，將curSum加入Map，并將其出現次數設置為1
if (map.has(curSum)) {?map.set(curSum, map.get(curSum) + 1)?
} else {?map.set(curSum, 1)?
}
- 繼續遞歸遍歷左右子樹：分別對當前節點的左子樹和右子樹進行遞歸調用，繼續計算子樹中的前綴和
root.left && deep(root.left, curSum)?
root.right && deep(root.right, curSum)
- 回溯：在遞歸返回時，需要進行回溯操作。因為我們已經遍歷完當前節點的子樹，要回到上一層節點繼續遍歷，所以需要將當前前綴和 curSum 的出現次數減 1 ，以保證 Map 中記錄的前綴和狀態只反映從根節點到當前層節點的情況
map.set(curSum, map.get(curSum) - 1)
難點-使用回溯
在本題實現的過程中，可能會忽略掉回溯的步驟
那么為什么需要回溯操作
模擬實現：考慮如下二叉樹（目標和 targetSum = -1）：
1/ \-2 -3
若無回溯：
- 遍歷根節點 1
- 前綴和 curSum = 1，差值 1 - (-1) = 2，map 中無 2，不計數
- map 狀態：{0:1, 1:1}
- 遞歸左子樹 -2
- 遍歷左子節點 -2
- 前綴和 curSum = 1 + (-2) = -1，差值 -1 - (-1) = 0，map 中存在 0（初始值），計數 + 1（路徑[1, -2]正確）。
- 未回溯時，
map狀態：{0:1, 1:1, -1:1}（保留 -1 的計數）。 - 左、右子樹為空，返回根節點
- 遞歸右子樹
-3- 前綴和
curSum = 1 + (-3) = -2，差值-2 - (-1) = -1 - 此時
map中存在-1（來自左子樹的記錄），算法錯誤認為存在路徑和為 -1，計數 + 1 - 錯誤結果：count = 2，但實際僅[1, -2]滿足條件
- 前綴和
其實在這里第三步中diff = -1此時map中不應該存在-1這一項，因為這里的map只是1->-3 ，卻把1->2的部分也存儲了起來，導致結果的不準確，使得1->2這條路徑重復計算，結果出錯
回溯的作用（有回溯時）
- 離開左子節點 -2 時，執行 map.set(-1, 0)，map 恢復為 {0:1, 1:1}。
- 遍歷右子樹 -3 時，前綴和 -2 的差值 -1 在 map 中無匹配，不計數。
- 正確結果：count = 1
實現
var pathSum = function (root, targetSum) {const map = new Map();map.set(0, 1);let count = 0; // 滿足條件的路徑const deep = (root, sum) => {if (!root) return;const curSum = sum + root.val;const diff = curSum - targetSumif (map.has(diff)) {count += map.get(diff);}if (map.has(curSum)) {map.set(curSum, map.get(curSum) + 1)} else {map.set(curSum, 1)}// 左root.left && deep(root.left, curSum)// 右root.right && deep(root.right, curSum)// 回溯map.set(curSum, map.get(curSum) - 1)}deep(root, 0)return count;
};
