문제 개요
이진 트리(binary tree)에서 뒤집기(flip) 연산이란 임의의 노드 하나를 선택하여 해당 노드의 왼쪽 자식 서브트리와 오른쪽 자식 서브트리를 서로 교환하는 것을 의미합니다.
두 이진 트리 X와 Y가 플립 등가(flip equivalent) 관계라는 것은, X에 대해 여러 번의 뒤집기 연산을 수행하여 Y를 만들어낼 수 있을 때, 그리고 오직 그 경우에만 성립합니다.
이번 글에서는 두 이진 트리가 서로 플립 등가인지 판별하는 메서드를 작성해 보겠습니다. 트리는 각각 루트 노드 root1과 root2로 주어집니다.
예시
다음과 같은 두 트리가 있다고 가정해 보겠습니다.
위 트리에서 값이 1, 3, 5인 노드들을 차례로 뒤집으면 두 트리가 동일한 형태가 됩니다. 따라서 출력 결과는 true(1)입니다.
알고리즘 접근 방법
이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 각 노드 쌍을 비교할 때, 왼쪽·오른쪽 자식을 그대로 비교하거나 뒤집어서 비교하는 두 가지 경우를 모두 고려하는 것입니다. 단계별로 살펴보면 다음과 같습니다.
- 두 트리 노드
t1,t2를 인자로 받는 재귀 함수solve()를 정의합니다. root1과root2가 모두 null이면true를 반환합니다. (두 트리 모두 빈 경우)- 둘 중 하나만 null이라면
false를 반환합니다. (구조가 다르므로) - 두 노드의 값이 다르면
false를 반환합니다. - (t1과 t2 모두 왼쪽 서브트리가 없는 경우) 또는 (t1과 t2 모두 왼쪽 서브트리가 존재하고, 두 왼쪽 자식의 값이 서로 같은 경우)에는 뒤집기 없이 비교합니다.
solve(root1의 왼쪽, root2의 왼쪽) AND solve(root1의 오른쪽, root2의 오른쪽) - 그 외의 경우에는 한쪽을 뒤집어서 비교합니다.
solve(root1의 왼쪽, root2의 오른쪽) AND solve(root1의 오른쪽, root2의 왼쪽)
C++ 구현 예제
아래 코드는 위 알고리즘을 그대로 구현한 전체 예제입니다.
#include <bits/stdc++.h>
using namespace std;
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) {
temp->left = new TreeNode(val);
return;
} else {
q.push(temp->left);
}
if (!temp->right) {
temp->right = new TreeNode(val);
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:
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
// 둘 다 null이면 등가
if (!root1 && !root2) return true;
// 한쪽만 null이면 등가 아님
else if (!root1 || !root2) return false;
// 노드 값이 다르면 등가 아님
else if (root1->val != root2->val) return false;
// 왼쪽 자식 구조가 일치하면 그대로 비교
else if ((!root1->left && !root2->left) ||
(root1->left && root2->left &&
root1->left->val == root2->left->val)) {
return flipEquiv(root1->left, root2->left) &&
flipEquiv(root1->right, root2->right);
}
// 그렇지 않으면 뒤집어서 비교
else {
return flipEquiv(root1->left, root2->right) &&
flipEquiv(root1->right, root2->left);
}
}
};
int main() {
vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8};
TreeNode *r1 = make_tree(v);
vector<int> v1 = {1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7};
TreeNode *r2 = make_tree(v1);
Solution ob;
cout << (ob.flipEquiv(r1, r2));
}실행 결과 확인
입력
[1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]
출력
1
출력값 1은 true를 의미하며, 두 트리가 플립 등가임을 나타냅니다.
복잡도 분석
- 시간 복잡도: O(N) — 각 트리의 모든 노드를 최대 한 번씩 방문합니다. N은 두 트리 중 더 작은 트리의 노드 수입니다.
- 공간 복잡도: O(H) — 재귀 호출 스택 깊이는 트리의 높이 H에 비례합니다. 최악의 경우(편향 트리) O(N)까지 증가할 수 있습니다.
마무리
플립 등가 판별 문제는 일반적인 이진 트리 동일성 검사에서 '자식 순서를 바꿔 비교하는 분기' 하나만 추가하면 해결됩니다. 재귀적 사고방식을 연습하기에 좋은 문제이며, 실제 코딩 테스트에서도 자주 등장하는 유형이니 위 구현 과정을 직접 따라 해 보시길 권장합니다.