C++ 이진 트리에서 주어진 두 레벨 사이의 모든 노드 출력하기

이 문제에서는 하나의 이진 트리(binary tree)와 트리 내의 두 개의 레벨(상위 레벨과 하위 레벨)이 주어지며, 상위 레벨과 하위 레벨 사이에 존재하는 모든 노드를 출력해야 합니다.

이진 트리는 각 노드가 최대 두 개의 자식 노드(0개, 1개 또는 2개)만 가질 수 있는 특수한 형태의 트리 구조입니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

상위 레벨(upper) − 3
하위 레벨(lower) − 1

출력 결과 −

6
3 9
7 4 8 10

문제 해결 접근 방법

이 문제를 해결하려면 지정된 레벨에 있는 트리의 노드들을 출력해야 합니다. 가장 단순한 방법은 하위 레벨부터 상위 레벨까지 반복문을 돌면서 각 레벨마다 재귀 함수를 호출하는 것입니다.

이 알고리즘은 구현이 간단하지만 시간 복잡도가 O(n²)으로 다소 비효율적입니다.

더 효율적인 해결책은 큐(queue)를 사용하여 레벨 순회(level order traversal, BFS)를 수행하고, 주어진 상위 레벨과 하위 레벨 범위 내에 있는 노드들만 출력하는 것입니다. 마커(marker) 노드를 활용해 레벨의 경계를 구분하면 각 레벨별로 노드를 깔끔하게 출력할 수 있습니다.

C++ 구현 예제

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
void printNodesAtLevel(Node* root, int low, int high){
    queue <Node *> Q;
    Node *marker = new Node;
    int level = 1;
    Q.push(root);
    Q.push(marker);
    while (Q.empty() == false){
        Node *n = Q.front();
        Q.pop();
        if (n == marker){
            cout << endl;
            level++;
            if (Q.empty() == true || level > high) break;
            Q.push(marker);
            continue;
        }
        if (level >= low)
            cout<<n->key<<" ";
        if (n->left != NULL) Q.push(n->left);
        if (n->right != NULL) Q.push(n->right);
    }
}
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
int main() {
    struct Node *root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->left = insertNode(7);
    root->left->right = insertNode(4);
    root->left->right->left = insertNode(8);
    root->left->right->right = insertNode(10);
    root->left->right->right->left = insertNode(5);
    root->left->right->right->right = insertNode(1);
    root->left->right->left->left = insertNode(14);
    root->left->right->left->right = insertNode(26);
    int upper = 3;
    int lower = 1;
    cout << "Level wise Nodes between level "<<lower<<" and "<<upper<<" are \n";
    printNodesAtLevel(root, lower, upper);
    return 0;
}

실행 결과

Level wise Nodes between level 1 and 3 are
6
3 9
7 4

위 코드에서는 큐에 루트 노드와 마커 노드를 먼저 넣은 후, 노드를 하나씩 꺼내며 자식 노드들을 큐에 추가합니다. 마커 노드를 만나면 한 줄을 바꾸고 레벨을 1 증가시키며, 현재 레벨이 하위 레벨(low)보다 크거나 같으면 해당 노드의 값을 출력합니다. 현재 레벨이 상위 레벨(high)을 초과하면 순회를 종료합니다.

이 방식을 사용하면 전체 트리를 한 번만 순회하므로 시간 복잡도는 O(n)이 되어, 재귀 호출 방식(O(n²))보다 훨씬 효율적입니다.