437. Path Sum III - Medium

前往題目

想法

• 毫無想法，說不定是要用什麼bottom-up之類的

思路

暴力解

1. DFS
2. 每個node都向下遞迴找尋符合sum的
3. 每次發現都紀錄，最後直接回傳counter就好

優化解

突然有個小小的領悟，DFS方法第一次被呼叫的時候最後一行return的就是最終的結果，可以想像成一開始只有一個點，然後這個點還會再呼叫dfs，每次呼叫dfs方法就會拓展一個子節點，最後遇到base case例如node == null後一個一個節點收回來最終變回一個點，然後return給一開始呼叫這個方法的地方

1. 用map紀錄prefix sum
2. DFS走遍所有nodes
3. 每到一個node都檢查map是否有對應的preSum，例如target是10，當前node是6，那需要preSum有4才能達到目標

Code

暴力解

// 暴力解
class Solution {
    int counter = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // Check current node
        helper(root, targetSum, 0L);
        // Go through all the nodes
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        
        return counter;
    }

    private void helper(TreeNode node, int targetSum, long curSum) {
        if (node == null) return;
        // Obtain current sum
        curSum += (long) node.val;
        // Found
        if (curSum == targetSum) ++counter;

        helper(node.left, targetSum, curSum);
        helper(node.right, targetSum, curSum);
    }
}

優化解

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // Store prefix sum
        Map<Long, Integer> map = new HashMap();
        map.put(0L, 1);
        return traverse(root, targetSum, 0L, map); 
    }

    private int traverse(TreeNode node, int targetSum, long preSum, Map<Long, Integer> map) {
        if (node == null) return 0;
        // Get current prefix sum
        preSum += node.val;
        // Check if preSum has the required value
        int res = map.getOrDefault(preSum - targetSum, 0);
        // Update prefix sum
        map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        res += traverse(node.left, targetSum, preSum, map) + traverse(node.right, targetSum, preSum, map);
        // Backtracking, because fall back to other nodes
        map.put(preSum, map.get(preSum) - 1);
        return res;
    }
}