[Binary Tree-DFS][Medium] Path Sum III

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

Path Sum III - LeetCode

 

Q. Tree 노드가 주어질때, 해당 노드의 leaf를 향하는 연속된 구간합이 targetSum 이 되는 구간의 빈도를 구하라.

 

Solution. 

  가장 직관적인 solution은 root에서 leaf로의 모든 dfs를 진행하면서 과정의 구간합이 target sum이 되는 구간을 찾고, 이 검색을 아래 다른 leaf들로 확장한다. 

   

   void dfs_search(TreeNode* node)

   {

           if(node == NULL) return;

           sum += node->value;

            if(sum == targetSum) 

                 ++retCount;

           dfs_search(node->left);

           dfs_search(node->right);

    }

   int pathSum(TreeNode* root)

   {

          dfs_seach(root);              // 루트를 기준으로 이 검색을 하고

          pathSum(root->left);        // 각 child들에게 이 검색을 다시 건다.

          pathSum(root->right);

    }

  

   그냥 봤을때 TC가 O(NxN) 혹은 최소 O(NxlogN)이 나온다. 

   뭔가 O(N)에 해결하는 더 좋은 알고리즘이 있을 것 같다. 

    

   음... 가만, 보니까 이 문제를 어디선가 본 것 같다. 

  https://artofcom77.tistory.com/198

[Good] 560. Subarray Sum Equals K

 

그렇다. 

 

  이 문제는 음수를 포함한, 구간합을 구하는 문제의 tree 버젼 인 것이다. 

  다시 문제로 돌아가서, 

  원 문제의 풀이대로, 풀어본다. 

 

void pathSum_helper(TreeNode* node, long sum, int& ret, unordered_map<long, int>& mapFreq, const int targetSum)
{
    if (node == NULL)	return;

    // Calculate Sum.
    sum += node->val;

    // Search.
    if (mapFreq.find(sum - targetSum) != mapFreq.end())
        ret += mapFreq[sum - targetSum];

    // Add to Buffer. 
    mapFreq[sum]++;

    // Keep Looping.
    pathSum_helper(node->left, sum, ret, mapFreq, targetSum);
    pathSum_helper(node->right, sum, ret, mapFreq, targetSum);

    mapFreq[sum]--;
    if (mapFreq[sum] == 0)
        mapFreq.erase(sum);
}
int pathSum(TreeNode* root, int targetSum)
{
    int ret = 0;
    unordered_map<long, int> mapFreq;
    mapFreq[0] = 1;
    pathSum_helper(root, 0, ret, mapFreq, targetSum);
    return ret;
}

 

 

다만, 이 문제에서 추가로 유의 해야 할 점은, 

sum의 범위를 long으로 해야 문제가 요구하는 범위 filter에 걸리지 않는다. 

또한, 

sum frequency map buffer를 함수에 pass in 해 줘야 하는데, 값으로 전달하냐, reference로 전달하느냐에 따라 속도 차이가 크다.

 

다음이 reference로 전달한 결과 이다. (8ms)

 

아래는 값으로 전달한 결과이다. (687ms)

 

아는 것 이상으로 차이가 크다. 

 

반드시 reference로 전달 하도록 한다.