문제 개요
이 문제에서는 두 개의 트리가 주어지며, 두 트리가 서로 동일한지 판단하는 코드를 작성하는 것이 목표입니다.
두 트리는 모든 노드의 값과 위치(구조)가 완전히 같을 때 동일(identical)하다고 정의합니다.
예시
위의 두 트리는 각 노드의 값과 배치가 완전히 일치하므로 동일한 트리입니다.
접근 방법
두 트리가 동일한지 확인하려면 루트 노드부터 시작하여 각 노드를 재귀적으로 순회하면서 단계별로 값을 비교합니다. 비교 과정 중 어느 시점이라도 두 노드가 일치하지 않으면 즉시 순회를 중단하고 두 트리가 동일하지 않음을 알립니다. 반대로 모든 노드를 성공적으로 통과하거나 두 트리가 모두 비어 있다면 두 트리는 동일한 것으로 판단합니다.
재귀 함수의 동작 로직은 다음과 같습니다.
- 두 노드가 모두 NULL인 경우: 해당 위치까지는 구조가 일치하므로 1(동일)을 반환합니다.
- 두 노드가 모두 NULL이 아닌 경우: 현재 노드의 데이터 값이 같은지 확인하고, 왼쪽 서브트리와 오른쪽 서브트리에 대해서도 재귀적으로 동일 여부를 검사합니다.
- 한쪽만 NULL이거나 값이 다른 경우: 0(동일하지 않음)을 반환합니다.
C++ 구현 예제
위에서 설명한 해결 방법의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return Node;
}
int isIdenticalTrees(node* tree1, node* tree2) {
if (tree1 == NULL && tree2 == NULL)
return 1;
if (tree1 != NULL && tree2 != NULL) {
return (tree1->data == tree2->data
&& isIdenticalTrees(tree1->left, tree2->left)
&& isIdenticalTrees(tree1->right, tree2->right));
}
return 0;
}
int main() {
node *root1 = insertNode(4);
node *root2 = insertNode(4);
root1->left = insertNode(5);
root1->right = insertNode(0);
root1->left->left = insertNode(1);
root1->left->right = insertNode(9);
root1->right->left = insertNode(7);
root2->left = insertNode(5);
root2->right = insertNode(0);
root2->left->left = insertNode(1);
root2->left->right = insertNode(9);
root2->right->left = insertNode(7);
cout << "Both the given trees are ";
if (isIdenticalTrees(root1, root2))
cout << "identical";
else
cout << "not identical";
return 0;
}
출력 결과
Both the given trees are identical
정리
이 알고리즘은 두 트리를 동시에 순회하면서 노드의 값과 구조를 비교하는 방식으로 동작합니다. 시간 복잡도는 두 트리의 노드 수에 비례하여 O(n)이며, 공간 복잡도는 재귀 호출 스택 깊이에 따라 최대 O(h)(h는 트리의 높이)입니다. 이 접근 방식은 이진 트리뿐만 아니라 일반적인 트리 구조의 동일성 검사에도 응용할 수 있습니다.