문제 소개
이진 트리가 하나 주어졌을 때, 노드 값들을 수직 순회(vertical order traversal)하는 문제를 살펴보겠습니다. 수직 순회란 트리를 위에서 아래로 내려다보았을 때 보이는 순서대로 노드를 방문하는 방식으로, 같은 열(column)에 위치한 노드들은 하나의 그룹으로 묶습니다. 만약 두 노드가 같은 행과 같은 열에 있다면, 순서는 반드시 왼쪽에서 오른쪽 방향이어야 합니다.
예를 들어 다음과 같은 이진 트리가 입력으로 주어지면,
각 노드의 열 좌표는 루트(3)가 0, 왼쪽 자식(9)이 -1, 오른쪽 자식(20)이 +1, 그리고 15는 -1+1=0, 7은 +1+1=+2가 됩니다. 따라서 기대하는 출력 결과는 다음과 같습니다.
[[9], [3, 15], [20], [7]]
해결 접근 방법
이 문제는 BFS(너비 우선 탐색)와 맵(map) 자료구조를 조합하면 깔끔하게 해결할 수 있습니다. 각 노드에 열 좌표(x)를 부여하고, 같은 열에 속한 노드 값들을 맵에 그룹화하는 것이 핵심 아이디어입니다. C++의 std::map은 키를 기준으로 자동 정렬되므로, 왼쪽 열부터 오른쪽 열까지 순서대로 결과를 얻을 수 있습니다.
알고리즘 단계
- 키가 정수인 맵
m을 정의합니다. - 노드와 열 좌표 x(기본값 0)를 받는
solve()함수를 정의합니다.- 노드가 null이거나 값이 0이면 즉시 반환합니다.
- 왼쪽 자식에 대해
solve(node->left, x - 1)을 재귀 호출합니다. - 오른쪽 자식에 대해
solve(node->right, x + 1)을 재귀 호출합니다. - 노드의 값을
m[x]벡터의 끝에 추가합니다.
- 메인 메서드(
verticalOrder)에서는 다음을 수행합니다.- 루트가 null이면 빈 결과를 반환합니다.
- 큐
q를 생성하고{ 0, root }쌍을 삽입한 뒤, 루트 값을m[0]에 추가합니다. - 큐가 빌 때까지 다음을 반복합니다.
sz := 큐의 현재 크기로 설정하고, sz가 0이 될 때까지 반복하며 매번 sz를 감소시킵니다.curr := 큐의 첫 번째 원소를 꺼내고 큐에서 제거합니다.node := curr.second(노드),x := curr.first(열 좌표)로 설정합니다.- 왼쪽 자식이 null이 아니고 값이 0이 아니라면,
{ x - 1, node->left }를 큐에 삽입하고 왼쪽 자식의 값을m[x - 1]에 추가합니다. - 오른쪽 자식이 null이 아니고 값이 0이 아니라면,
{ x + 1, node->right }를 큐에 삽입하고 오른쪽 자식의 값을m[x + 1]에 추가합니다.
- 2차원 배열
ret을 정의하고, 맵m의 각 키-값 쌍을 순회하며 값을ret에 삽입한 후 반환합니다.
C++ 구현 코드
아래 구현 예제를 통해 동작 방식을 더 명확히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int>> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << "[";
for(int j = 0; j < v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]" << endl;
}
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:
map<int, vector<int>> m;
void solve(TreeNode* node, int x = 0){
if (!node || node->val == 0)
return;
solve(node->left, x - 1);
solve(node->right, x + 1);
m[x].push_back(node->val);
}
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
}
vector<vector<int>> verticalOrder(TreeNode* root){
if (!root)
return {};
queue<pair<int, TreeNode*>> q;
q.push({ 0, root });
m[0].push_back(root->val);
while (!q.empty()) {
int sz = q.size();
while (sz--) {
pair<int, TreeNode*> curr = q.front();
q.pop();
TreeNode* node = curr.second;
int x = curr.first;
if (node->left && node->left->val != 0) {
q.push({ x - 1, node->left });
m[x - 1].push_back(node->left->val);
}
if (node->right && node->right->val != 0) {
q.push({ x + 1, node->right });
m[x + 1].push_back(node->right->val);
}
}
}
vector<vector<int>> ret;
map<int, vector<int>>::iterator it = m.begin();
while (it != m.end()) {
ret.push_back(it->second);
it++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,9,20,NULL,NULL,15,7};
TreeNode *root = make_tree(v);
print_vector(ob.verticalOrder(root));
}
실행 결과 확인
입력
{3,9,20,NULL,NULL,15,7}
출력
[[9],[3, 15],[20],[7]]
결과를 보면 가장 왼쪽 열(-1)에는 노드 9, 중앙 열(0)에는 노드 3과 15가 왼쪽에서 오른쪽 순서로 배치되고, 오른쪽 열(+1)에는 노드 20, 가장 오른쪽 열(+2)에는 노드 7이 순서대로 출력됩니다.
복잡도 분석
시간 복잡도: O(n log n) — 모든 노드를 한 번씩 방문하며(O(n)), 맵에 삽입할 때마다 log n의 정렬 비용이 발생하기 때문입니다.
공간 복잡도: O(n) — 모든 노드 값을 맵과 큐에 저장해야 하므로 노드 수에 비례하는 공간이 필요합니다.
이처럼 BFS와 정렬된 맵을 활용하면 이진 트리의 수직 순회를 직관적이고 효율적으로 구현할 수 있습니다. 특히 같은 열의 노드를 상하 관계와 무관하게 왼쪽에서 오른쪽 순서로 처리해야 하는 요구 사항이 있을 때 이 접근 방식이 유용합니다.