C++로 구현하는 이진 트리 레벨 순서 순회(Level Order Traversal) 프로그램

개요

이진 트리(Binary Tree)가 하나 주어져 있다고 가정해 보겠습니다. 이 트리를 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS) 방식으로 순회해야 합니다.

예를 들어 트리가 다음과 같은 구조라면,

레벨 순서대로 방문한 결과는 다음과 같습니다.

[1, 2, 3, 5, 4]

해결 접근 방법

레벨 순서 순회는 큐(Queue) 자료구조를 활용하면 간단하게 구현할 수 있습니다. 알고리즘의 동작 단계는 다음과 같습니다.

• 노드를 저장할 큐(que)를 정의합니다.

• 루트(root) 노드를 큐에 삽입합니다.

• 큐가 비어 있지 않은 동안 아래 과정을 반복합니다.

  • item := 큐의 맨 앞(front)에 있는 노드

  • item의 값을 출력(또는 결과 벡터에 저장)

  • item의 왼쪽 자식이 NULL이 아니면 큐에 삽입

  • item의 오른쪽 자식이 NULL이 아니면 큐에 삽입

  • 큐에서 맨 앞 요소를 삭제(pop)

큐의 선입선출(FIFO) 특성 덕분에 같은 레벨의 노드들이 왼쪽부터 오른쪽 순서로 처리되며, 그다음 레벨로 자연스럽게 넘어가게 됩니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = right = NULL;
        }
};

class Solution {
    public:
    vector<int> solve(TreeNode* root) {
        if(!root)
            return {};
        vector <int> ret;
        queue <TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            ret.push_back(node->val);
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        return ret;
    }
};

main(){
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
}

입력

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);

출력

[1, 2, 3, 5, 4]

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(N) — 모든 노드를 정확히 한 번씩 방문합니다.

• 공간 복잡도: O(W) — W는 트리의 최대 너비로, 한 레벨에 존재할 수 있는 최대 노드 수만큼 큐에 저장됩니다. 최악의 경우 O(N)입니다.