이진 트리가 주어졌을 때, 해당 트리가 완전 이진 트리(Complete Binary Tree)인지 판별하는 문제를 살펴보겠습니다.
완전 이진 트리란 깊이가 n인 트리에서 레벨 0부터 n-1까지는 모든 노드가 가득 차 있고, 가장 아래 레벨 n의 노드들은 반드시 왼쪽부터 순서대로 채워져야 하는 트리를 의미합니다.
예를 들어 다음과 같은 트리가 입력으로 주어지면,
모든 노드가 위 조건을 만족하므로 출력은 true가 됩니다.
문제 해결 접근 방법
이 문제는 BFS(너비 우선 탐색)와 플래그 변수를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "한 번이라도 자식이 비어 있는 노드를 만나면, 그 이후에 등장하는 어떤 노드도 자식을 가질 수 없다"는 것입니다.
알고리즘의 동작 단계는 다음과 같습니다.
- 트리가 비어 있으면 true를 반환합니다.
- 큐 q를 생성하고 루트 노드를 삽입한 뒤, 플래그(flag)를 true로 설정합니다.
- 큐에 요소가 남아 있는 동안 다음을 반복합니다.
- sz := 큐의 현재 크기
- sz가 0이 될 때까지 다음을 반복합니다.
- 큐에서 노드를 하나 꺼냅니다.
- 노드에 왼쪽 자식이 있는 경우 → 플래그가 true이면 왼쪽 자식을 큐에 삽입하고, 플래그가 false라면 즉시 false를 반환합니다. 왼쪽 자식이 없다면 플래그를 false로 설정합니다.
- 노드에 오른쪽 자식이 있는 경우 → 플래그가 true이면 오른쪽 자식을 큐에 삽입하고, 플래그가 false라면 즉시 false를 반환합니다. 오른쪽 자식이 없다면 플래그를 false로 설정합니다.
- sz를 1 감소시킵니다.
- 모든 검사를 통과하면 true를 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#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){
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:
bool isCompleteTree(TreeNode* root) {
if(!root)return true;
queue <TreeNode*> q;
q.push(root);
bool isComplete = true;
while(!q.empty()){
int sz = q.size();
while(sz--){
TreeNode* node = q.front();
q.pop();
if(node->left){
if(isComplete){
q.push(node->left);
}else return false;
}else{
isComplete = false;
}
if(node->right){
if(isComplete){
q.push(node->right);
}else return false;
}else{
isComplete = false;
}
}
}
return true;
}
};
main(){
vector<int> v = {1,2,3,4,5,6};
TreeNode *r1 = make_tree(v);
Solution ob;
cout << (ob.isCompleteTree(r1));
}입력
{1,2,3,4,5,6}출력
1
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 큐에는 최악의 경우 트리의 마지막 레벨 노드들이 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다.