문제 개요
트리의 루트(root)가 주어졌을 때, 가장 빈번하게 등장하는 서브트리 합(most frequent subtree sum)을 찾아야 합니다.
여기서 '서브트리 합'이란 특정 노드를 루트로 하는 서브트리에 포함된 모든 노드 값(해당 노드 자신 포함)의 합을 의미합니다. 만약 최빈값이 여러 개라면, 가장 높은 빈도를 가진 모든 값을 임의의 순서로 반환하면 됩니다.
예를 들어 트리가 [5, 2, -5]와 같이 구성되어 있다면 결과는 [2]가 됩니다. 그 이유는 각 노드의 서브트리 합을 계산해 보면 다음과 같습니다.
- 노드 2의 서브트리 합 = 2
- 노드 -5의 서브트리 합 = -5
- 루트 5의 서브트리 합 = 5 + 2 + (-5) = 2
즉, 합 2는 두 번 등장하지만 -5는 한 번만 등장하기 때문에 정답은 [2]입니다.
해결 알고리즘
이 문제는 후위 순회(postorder traversal)와 해시 맵을 조합하여 효율적으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
두 개의 맵을 정의합니다.
m은 정수 키에 해당하는 리스트를 저장하고,freq는 각 합의 빈도수를 저장합니다.트리 노드를 인자로 받는
solve()메서드를 정의합니다. 동작 방식은 다음과 같습니다.노드가 null이면 0을 반환합니다.
leftSum := solve(node.left),rightSum := solve(node.right)로 왼쪽과 오른쪽 서브트리의 합을 재귀적으로 구합니다.currSum := node.val + leftSum + rightSum으로 현재 노드의 서브트리 합을 계산합니다.currSum이 처음 등장한 경우(freq에 존재하지 않으면):m[1]에 해당하는 리스트에currSum을 삽입합니다.freq[currSum] := 1로 설정합니다.
이미 등장했던 경우:
freq[currSum]을 1 증가시킵니다.m[freq[currSum]]에 해당하는 리스트에currSum을 삽입합니다.
currSum을 반환합니다.메인 메서드(
findFrequentTreeSum)의 흐름은 다음과 같습니다.루트가 null이면 빈 집합을 반환합니다.
solve(root)를 호출합니다.맵
m에서 마지막(가장 큰 빈도 키) 리스트를 반환합니다.
C++의 std::map은 키를 오름차순으로 정렬하여 저장하므로, rbegin()을 사용하면 가장 큰 빈도 키에 해당하는 값을 손쉽게 얻을 수 있다는 점이 이 구현의 핵심입니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
map <int, vector <int> > m;
map <int, int > freq;
int solve(TreeNode* node){
if(!node)return 0;
int leftSum = solve(node->left);
int rightSum = solve(node->right);
int currSum = node->val + leftSum + rightSum;
if(!freq.count(currSum)){
m[1].push_back(currSum);
freq[currSum] = 1;
} else {
freq[currSum]++;
m[freq[currSum]].push_back(currSum);
}
return currSum;
}
vector<int> findFrequentTreeSum(TreeNode* root) {
m.clear();
freq.clear();
if(!root)return {};
solve(root);
return m.rbegin()->second;
}
};
main(){
vector<int> v = {5,2,-5};
TreeNode *tree = make_tree(v);
Solution ob;
print_vector(ob.findFrequentTreeSum(tree));
}입력
[5,2,-5]
출력
[2]
복잡도 분석
이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)이며, N은 노드의 개수입니다. 공간 복잡도 역시 빈도 정보를 저장하는 맵 때문에 O(N)입니다.