이진 트리(binary tree)가 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 일은 이 트리 안에 중복된 서브트리(하위 트리)가 존재하는지 확인하고, 있다면 해당 서브트리들을 모두 찾아내는 것입니다.
예를 들어 아래와 같은 이진 트리가 있다고 합시다.
이 트리에는 크기 2짜리 동일한 서브트리가 두 개 존재합니다. 또한 각 서브트리 내부를 살펴보면, 노드 D 그 자체와 BD, BE 역시 중복되는 서브트리에 해당합니다.
접근 방법: 트리 직렬화와 해싱
이 문제는 트리 직렬화(serialization)와 해싱(hashing) 기법을 활용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
1. 각 서브트리를 고유한 문자열로 직렬화합니다. 이때 중위 순회(inorder traversal) 결과를 문자열로 만들고, 빈 노드(null) 위치에는 여는 괄호와 닫는 괄호를 삽입하여 트리의 구조를 명확하게 표현합니다.
2. 직렬화된 문자열을 해시 맵(unordered_map)에 저장하면서, 동일한 문자열이 몇 번 등장했는지 개수를 세어 줍니다.
3. 어떤 서브트리의 직렬화 결과가 이미 한 번 등장했다면(map[str] == 1), 그 서브트리의 루트 노드는 중복 서브트리의 루트이므로 출력 대상이 됩니다.
C++ 구현 예제
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const char MARKER = '$';
struct Node {
public:
char data;
Node *left, *right;
};
Node* getNode(char key) {
Node* newNode = new Node;
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
unordered_set<string> subtrees;
string inorder(Node* node, unordered_map<string, int>& map) {
if (!node)
return "";
string str = "(";
str += inorder(node->left, map);
str += to_string(node->data);
str += inorder(node->right, map);
str += ")";
if (map[str] == 1)
cout << node->data << " ";
map[str]++;
return str;
}
void duplicateSubtreeFind(Node *root) {
unordered_map<string, int> map;
inorder(root, map);
}
int main() {
Node *root = getNode('A');
root->left = getNode('B');
root->right = getNode('C');
root->left->left = getNode('D');
root->left->right = getNode('E');
root->right->right = getNode('B');
root->right->right->right = getNode('E');
root->right->right->left= getNode('D');
duplicateSubtreeFind(root);
}실행 결과
D E B
코드 설명
inorder() 함수는 재귀적으로 각 노드를 방문하며 서브트리를 직렬화합니다. 왼쪽 자식의 직렬화 결과, 현재 노드의 데이터, 오른쪽 자식의 직렬화 결과를 순서대로 이어 붙이고 전체를 괄호로 감싸서 반환합니다. 이렇게 하면 구조가 같은 서브트리는 항상 동일한 문자열을 갖게 됩니다.
직렬화된 문자열이 해시 맵에 처음 등장한 것이 아니라 정확히 한 번만 등장한 상태라면(map[str] == 1), 지금 방문한 노드는 중복 서브트리의 루트이므로 화면에 출력됩니다. 이후 map[str]++로 등장 횟수를 증가시켜, 같은 서브트리가 세 번째 등장할 때는 다시 출력되지 않도록 처리합니다.
예제 실행 결과 D E B가 출력되는데, 이는 노드 D 자체, 그리고 루트가 B인 두 개의 동일한 서브트리(BD, BE)가 중복으로 발견되었음을 의미합니다.