이진 트리(binary tree)가 주어졌을 때, 모든 중복 서브트리(duplicate subtrees)를 찾아야 합니다. 여기서 각 종류의 중복 서브트리마다 그중 하나의 루트 노드만 반환하면 됩니다.
예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.
이 트리에서 찾을 수 있는 중복 서브트리는 다음과 같습니다.
해결 접근 방식
이 문제의 핵심 아이디어는 각 서브트리를 고유한 문자열로 직렬화(serialize)하는 것입니다. 동일한 구조와 값을 가진 서브트리는 반드시 동일한 문자열 표현을 갖게 되므로, 해시 맵을 이용해 등장 횟수를 세면 중복을 쉽게 판별할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- 결과를 저장할 배열
ret과 서브트리 문자열의 등장 횟수를 기록할 맵(map)m을 생성합니다. - 노드를 입력으로 받는 재귀 함수
solve()를 정의합니다. 이 함수는 다음과 같이 동작합니다. - 노드가 null이면 "-1"을 반환합니다. (빈 자식 노드 구분용)
- 현재 노드의 값을 문자열로 변환한 뒤, 구분자 "#"을 붙입니다.
- 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로
solve()를 호출하여 각각left,right에 저장합니다. - 문자열 x에 left와 right를 구분자와 함께 이어 붙여 현재 서브트리의 고유한 직렬화 표현을 만듭니다.
- 맵
m에서 해당 문자열의 카운트를 1 증가시킵니다. - 카운트가 정확히 2가 되는 순간(즉, 두 번째로 발견되었을 때) 해당 노드를
ret에 삽입합니다. 이렇게 하면 같은 서브트리가 세 번 이상 나타나도 중복 추가를 방지할 수 있습니다. - 직렬화된 문자열 x를 상위 호출로 반환합니다.
마지막으로 메인 함수에서 solve(root)를 호출하고 ret을 반환하면 됩니다.
시간 복잡도
모든 노드를 한 번씩 방문하며 각 단계에서 문자열 연결이 발생하므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도 역시 직렬화 문자열을 저장하기 위해 O(n²)까지 증가할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0 || curr == NULL){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
vector <TreeNode*> ret;
map <string, int> m;
string solve(TreeNode* node){
if(!node || node->val == 0){
return "-1";
}
string x = to_string(node->val);
x += "#";
string left = solve(node->left);
string right = solve(node->right);
x = x + "#" + left + "#" + right;
m[x]++;
if(m[x] == 2){
ret.push_back(node);
}
return x;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
ret.clear();
m.clear();
solve(root);
return ret;
}
};
main(){
vector<int> v = {1,2,3,4,NULL,2,4,NULL,NULL,NULL,NULL,4};
Solution ob;
TreeNode *root = make_tree(v);
vector<TreeNode*> trees = ob.findDuplicateSubtrees(root);
for(TreeNode *t : trees){
tree_level_trav(t);
}
}실행 결과
입력
[1,2,3,4,null,2,4,null,null,null,null,4]
출력
[4] [2, 4]
출력 결과를 보면 값 4를 가진 리프 노드 서브트리 하나와, 루트가 2이고 오른쪽 자식으로 4를 가지는 서브트리 하나, 총 두 개의 중복 서브트리가 올바르게 검출된 것을 확인할 수 있습니다.