437. Path Sum III

Link

Solution

融合用hashMap找區間sum值 & tree的特性

1. 若中間有個節點preNode到達currentNode的sum值可滿足target，則從root到preNode的sum值(preSum) 與 從 root 到currentNode的sum值(currentSum)關係為:

$$target = currentSum - preSum$$

2. 所以當想知道以currentNode為結尾，解滿足sum值 = target 的path數目，就只到找到有幾個滿足(preSum = currentSum - target)的path。

3. 根據以上觀察可以使用DFS的方式將所有node的currentSum加入hashMap， 其中key是sum值，value是出現次數。並在過程中尋找是某有滿足條件的preSum以在map中。若有就將他的value值帶入return value中。

class Solution {
    public int pathSum(TreeNode root, int sum) {
       Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int ret = helper(map, 0, sum, root);
        return ret;
    }
    
    public int helper(Map<Integer, Integer> map, int currentSum, int target, TreeNode node){
        if(node == null) return 0;
        
        currentSum += node.val;
        int res = map.getOrDefault(currentSum - target, 0); //以目前currentNode為結尾的path數
        
        map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
        res += helper(map, currentSum, target, node.left) //往左子樹看其他可能 
            + helper(map, currentSum, target, node.right); //往右子樹看其他可能
        map.put(currentSum, map.get(currentSum) - 1); //考慮另一個不包含currentNode的path，比方說切換到另一個子樹
        return res;
    }
}