Leetcode - 437. Path Sum III 풀이

문제

주어진 트리에서 root부터 leaf까지 path중에 합이 targetSum 과 같은 경우는 총 몇개인가 (root부터 시작될 필요 없음)

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

https://leetcode.com/problems/path-sum-iii/

해결 아이디어

• 기본적으로 560. Subarray Sum Equals K 와 동일하다. 560번 문제를 먼저 잘 이해하면, 이 문제도 쉽게 해결할 수 있다. 이 두문제를 항상 쌍으로 같이 풀어볼것.
  • 다른점은 리스트를 선형적으로 순회하는 대신, 트리의 모든 노드를 순회하는 방식이다. (이 두 구조의 차이에 따라 동일한 구조를 순회하는 방식이 아주 흥미로웠다)
• 마치 백트래킹 기법의 tmp벡터처럼, 재귀 호출을 하기전에 해시테이블의 값을 증가하고, 재귀 호출이 끝나면 감소 시킨다. 그러면 root-> leef까지 하나의 path에서 subarray-sum을 구하는것과 동일하다.

해결

• -10^9 <= Node.val <= 10^9 이기 때문에 newsum이 int면 overflow가 발생할수 있다. 따라서 long int 로. (실수 한 부분)

class Solution {
    int count;
    unordered_map<long int, int> freq;
public:
    void dfs(TreeNode* root, int tgt, long int sum) {
        if (root == NULL)
            return;
        long int newsum = sum + root->val;
        if (freq.find(newsum - tgt) != freq.end()) {
            count += freq[newsum - tgt];
        }
        freq[newsum]++;
        dfs(root->left, tgt, newsum);
        dfs(root->right, tgt, newsum);
        freq[newsum]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        freq[0] = 1;
        dfs(root, targetSum, 0);
        return count;
    }
};