이진 트리가 하나 주어졌을 때, 해당 트리의 최대 너비(maximum width)를 구하는 함수를 정의해야 합니다. 여기서 트리의 너비란 모든 레벨(층) 중에서 가장 넓은 레벨의 너비를 의미합니다.
이 문제에서 이진 트리는 완전 이진 트리와 동일한 구조를 기준으로 하되, 일부 노드가 null일 수 있다고 가정합니다. 한 레벨의 너비는 그 레벨의 양 끝 노드, 즉 가장 왼쪽에 있는 null이 아닌 노드와 가장 오른쪽에 있는 null이 아닌 노드 사이의 길이로 정의되며, 두 끝 노드 사이에 존재하는 null 노드들도 길이 계산에 포함됩니다.
예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.
위 트리의 마지막 레벨은 [5, 3, null, 9]이므로, null 노드까지 포함한 길이가 4가 되어 전체 트리의 최대 너비는 4입니다.
해결 접근 방법
이 문제는 레벨 순회(BFS)와 인덱스 부여 기법을 활용하면 효율적으로 해결할 수 있습니다. 각 노드에 완전 이진 트리에서의 위치를 나타내는 인덱스를 부여하고, 같은 레벨에서 첫 번째 노드와 마지막 노드의 인덱스 차이를 이용해 너비를 계산합니다.
ans := 1,size := 0으로 초기화합니다.(노드, 값) 쌍을 저장할 양방향 큐(deque)
q를 정의합니다.(root, 1)을q에 삽입합니다.q가 비어 있지 않은 동안 다음을 반복합니다.size := q의 크기(노드, 값) 쌍
curr을 정의합니다.size가 1이면, (큐 맨 앞 요소의 노드, 1)을q에 삽입한 후 맨 앞 요소를 삭제합니다. 즉, 현재 레벨에 노드가 하나뿐이라면 너비를 1로 재설정합니다.size가 0이 아닌 동안 다음을 반복합니다.curr := q의 맨 앞 요소, 그리고 맨 앞 요소를 삭제합니다.curr노드의 왼쪽 자식이 null이 아니라면, (왼쪽 자식, 2 × curr의 값)을 만들어q에 삽입합니다.curr노드의 오른쪽 자식이 null이 아니라면, (오른쪽 자식, 2 × curr의 값 + 1)을 만들어q에 삽입합니다.q의 크기가 1보다 크다면,ans := max(ans, q의 마지막 요소 값 − q의 첫 번째 요소 값 + 1)로 갱신합니다.size := size − 1
ans를 반환합니다.
핵심 아이디어는 왼쪽 자식에게는 부모 인덱스의 2배, 오른쪽 자식에게는 부모 인덱스의 2배 + 1을 부여하는 것입니다. 이렇게 하면 null 노드가 있어도 마치 완전 이진 트리처럼 각 노드의 상대적 위치를 추적할 수 있습니다.
예제 코드
아래 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){
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:
int widthOfBinaryTree(TreeNode* root) {
int ans = 0;
deque < pair <TreeNode*, int> > q;
q.push_back({root,1});
ans = 1;
int size;
while(!q.empty()){
size = q.size();
pair <TreeNode*, int> curr;
if(size == 1){
q.push_back({q.front().first, 1});
q.pop_front();
}
while(size--){
curr = q.front();
q.pop_front();
if(curr.first->left){
q.push_back({curr.first->left, 2 * curr.second});
}
if(curr.first->right){
q.push_back({curr.first->right, 2 * curr.second + 1});
}
}
if(q.size() > 1)
ans = max(ans, q.back().second - q.front().second + 1);
}
return ans;
}
};
main(){
vector<int> v = {1,3,2,5,3,NULL,9};
TreeNode *root = make_tree(v);
Solution ob;
cout << (ob.widthOfBinaryTree(root));
}
입력
[1,3,2,5,3,null,9]
출력
4
복잡도 분석
시간 복잡도: O(N) — 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(N) — 큐에는 임의의 한 레벨에 속한 노드들이 최대로 저장됩니다.
참고로 트리의 깊이가 매우 깊어지면 인덱스 값이 지수적으로 증가하여 정수 오버플로가 발생할 수 있습니다. 실제 환경에서는 unsigned long long 타입을 사용하거나, 각 레벨의 첫 번째 노드 인덱스를 기준으로 상대적인 값을 계산하도록 정규화하는 것이 안전합니다.