이번 글에서는 이진 트리가 레벨(level) 단위로 정렬되어 있는지 확인하는 방법을 알아보겠습니다. 레벨별로 정렬된 이진 트리는 다음과 같은 형태를 가집니다.
레벨별 정렬된 이진 트리란?
레벨별로 정렬된 이진 트리는 두 가지 조건을 만족해야 합니다.
- 각 레벨 내에서 노드들이 왼쪽에서 오른쪽 방향으로 오름차순으로 정렬되어 있어야 합니다.
- 상위 레벨의 모든 노드 값이 하위 레벨의 모든 노드 값보다 작아야 합니다. 즉, 아래로 내려갈수록 값이 커집니다.
해결 접근 방법
이 문제는 레벨 순서 순회(Level Order Traversal), 즉 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
1. 큐(queue)를 사용하여 트리를 레벨 단위로 순회합니다.
2. 현재 레벨의 최솟값(min_val)과 최댓값(max_val)을 추적합니다.
3. 별도의 변수 prev_max에 이전 레벨의 최댓값을 저장해 둡니다.
4. 현재 레벨의 최솟값이 prev_max보다 크다면, 현재 레벨까지는 레벨별로 정렬된 상태입니다. 그렇지 않으면 정렬 조건을 만족하지 않으므로 false를 반환합니다.
5. prev_max를 현재 레벨의 최댓값으로 갱신한 후, 모든 레벨을 순회할 때까지 위 과정을 반복합니다.
모든 레벨에서 조건을 통과하면 해당 트리는 레벨별로 정렬된 이진 트리입니다.
C++ 구현 예제
#include <iostream>
#include <queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLevelWiseSorted(Node* root) {
int prevMax = INT_MIN;
int min_val, max_val;
int levelSize;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
levelSize = q.size();
min_val = INT_MAX;
max_val = INT_MIN;
while (levelSize > 0) {
root = q.front();
q.pop();
levelSize--;
min_val = min(min_val, root->key);
max_val = max(max_val, root->key);
if (root->left)
q.push(root->left);
if (root->right)
q.push(root->right);
}
if (min_val <= prevMax)
return false;
prevMax = max_val;
}
return true;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
if (isLevelWiseSorted(root))
cout << "Tree is levelwise Sorted";
else
cout << "Tree is Not levelwise sorted";
}실행 결과
Tree is level wise Sorted
코드 설명 및 시간 복잡도
위 코드에서는 먼저 1부터 7까지의 값을 가지는 완전 이진 트리를 생성합니다. 첫 번째 레벨은 {1}, 두 번째 레벨은 {2, 3}, 세 번째 레벨은 {4, 5, 6, 7}로 구성되어 있으며, 각 레벨 내에서 왼쪽에서 오른쪽으로 값이 증가하고 상위 레벨보다 값이 크므로 레벨별로 정렬된 트리입니다.
isLevelWiseSorted 함수는 큐를 이용해 각 레벨의 노드 개수만큼만 반복 처리하며, 레벨이 끝날 때마다 최솟값과 이전 레벨의 최댓값을 비교합니다. 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 여기서 n은 트리의 전체 노드 개수입니다.