[Binary Tree - DFS, Medium] Path Sum III

https://leetcode.com/problems/path-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75

이전 문제와 비슷한 것 같지만, 단순히 max만 구할 게 아니라 누계 sum을 구해야 한다.

처음에는 List 형태로 가지고 다니면서 재귀 전에 넣고 재귀 후에 빼는 것을 생각해 봤으나 관리가 쉽지 않음
결국 솔루션 참고해서 Map과 키를 보수 형태로 사용하면 관리가 편하다는 점을 찾았다.

Map은 <pathSum, count>형태로 관리한다.
key를 보수로 조회했을 때 찾아진다면, 해당 카운트는 정답이 될 수 있는 범위기 때문에 더해줘야 함

• 만약 pathSum - targetSum 로 키를 조회했을 때 찾아진다면 해당 카운트를 더한다 (현재 pathSum의 보수기 때문에 그것만 빼면 targetSum이 된다)

그 외에도 현재 pathSum이 targetSum과 같으면 카운트를 1 증가시킨다.

dfs 순회 전에 맵에 pathSum 키로 값을 넣어주고
dfs 순회 이후에는 맵에서 제거해서 중복되지 않도록 한다.

class Solution {
    int cnt = 0;
    public int pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, 0, new HashMap<>());
        return cnt;
    }

    public void dfs(TreeNode node, int targetSum, long pathSum, Map<Long, Integer> pathsMap) {
        if (node == null) {
            return;
        }

        pathSum += node.val;

        if (pathsMap.containsKey(pathSum - targetSum)) {
            cnt += pathsMap.get(pathSum - targetSum);
        }

        if (targetSum == pathSum) {
            cnt++;
        }

        pathsMap.put(pathSum, pathsMap.getOrDefault(pathSum, 0) + 1);

        dfs(node.left, targetSum, pathSum, pathsMap);
        dfs(node.right, targetSum, pathSum, pathsMap);

        pathsMap.put(pathSum, pathsMap.get(pathSum) - 1);
    }
}