C++로 이진 트리의 특정 수직 레벨이 정렬되어 있는지 확인하는 방법

개념

주어진 이진 트리에서 특정 수직 레벨(vertical level)이 정렬되어 있는지 판별하는 것이 이 글의 목표입니다.

여기서 주의할 점은, 두 노드가 서로 겹치는 경우 해당 노드들이 속한 레벨에서 정렬된 순서를 이루는지 함께 검증해야 한다는 것입니다.

입력 예시 1

출력

Yes

레벨 -1에 속한 노드들은 3 → 7 순서로 배치되어 있으며, 정렬된 수열을 이룹니다.

입력 예시 2

출력

Yes

값이 4와 5인 두 노드는 이진 트리에서 서로 겹쳐 있습니다. 이런 경우에도 레벨별로 정렬된 수열을 이루는지 확인해야 하며, 실제로 레벨 0의 노드들은 2 → 4 → 5 순서로 정렬된 수열을 이루므로 답은 "Yes"입니다.

접근 방법

1. 단순한 해법

이진 트리를 레벨 순회(level order traversal)하면서 각 수직 레벨을 별도의 배열에 저장한 뒤, 레벨 l에 해당하는 배열이 정렬되어 있는지 확인합니다. 다만 이 방법은 모든 레벨의 노드를 저장해야 하므로 메모리 사용량이 크다는 단점이 있어, 이를 줄일 필요가 있습니다.

2. 효율적인 해법

이진 트리를 수직 레벨 순회하면서 레벨 l에 속한 노드 값만 추적합니다. 이전 원소가 현재 원소보다 작거나 같으면 정렬된 수열이 유지됩니다. 순회 도중 레벨 l의 이전 값을 저장해 두고, 레벨 l에 속한 현재 노드 값과 비교합니다.

현재 노드 값이 이전 값보다 크거나 같으면 → 레벨 l이 끝날 때까지 같은 과정을 반복합니다.
중간에 현재 노드 값이 이전 값보다 작아지면 → 레벨 l은 정렬되어 있지 않습니다.
레벨 l의 끝까지 도달하면 → 해당 레벨은 정렬된 것입니다.

C++ 구현 예제

// C++ 프로그램: 이진 트리의
// 수직 레벨 l이 정렬되어 있는지 판별합니다.
#include <bits/stdc++.h>
using namespace std;

// 트리 노드 구조체
struct Node1 {
    int key1;
    Node1 *left1, *right1;
};

// 새 트리 노드를 생성하는 함수
Node1* newNode(int key1){
    Node1* temp1 = new Node1;
    temp1->key1 = key1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

// 주어진 이진 트리의 수직 레벨 l이
// 정렬되어 있는지 확인하는 헬퍼 함수
bool isSorted1(Node1* root1, int level1){
    // 루트가 NULL이면 빈 집합을 의미하며,
    // 빈 집합은 항상 정렬된 것으로 간주됩니다.
    if (root1 == NULL)
        return true;

    // 수직 레벨 l의 이전 값을 저장하는 변수
    int prevVal1 = INT_MIN;

    // 트리를 수직으로 순회하는 동안
    // 현재 레벨을 저장하는 변수
    int currLevel1;

    // 트리를 수직으로 순회하는 동안
    // 현재 노드를 저장하는 변수
    Node1* currNode1;

    // 수직 순회를 수행하기 위한 큐 선언.
    // 큐의 원소는 pair이며, 첫 번째 원소는 노드,
    // 두 번째 원소는 해당 노드의 수직 레벨을 나타냅니다.
    queue<pair<Node1*, int>> q1;

    // 루트를 큐에 삽입합니다. 루트의 수직 레벨은 0입니다.
    q1.push(make_pair(root1, 0));

    // 모든 노드를 방문할 때까지 수직 순회를 수행합니다.
    while (!q1.empty()) {
        currNode1 = q1.front().first;
        currLevel1 = q1.front().second;
        q1.pop();

        // 큐에서 꺼낸 노드의 레벨이 요구된 레벨과 같은지 확인합니다.
        // 같다면 그 레벨의 이전 값이 현재 노드 값보다
        // 작거나 같은지 검사합니다.
        if (currLevel1 == level1) {
            if (prevVal1 <= currNode1->key1)
                prevVal1 = currNode1->key1;
            else
                return false;
        }

        // 왼쪽 자식이 NULL이 아니면
        // 레벨을 1 감소시켜 큐에 삽입합니다.
        if (currNode1->left1)
            q1.push(make_pair(currNode1->left1, currLevel1 - 1));

        // 오른쪽 자식이 NULL이 아니면
        // 레벨을 1 증가시켜 큐에 삽입합니다.
        if (currNode1->right1)
            q1.push(make_pair(currNode1->right1, currLevel1 + 1));
    }

    // 요청된 레벨이 트리에 존재하지 않으면
    // 해당 레벨은 빈 집합이 되므로 답은 true입니다.
    return true;
}

// 드라이버 코드
int main(){
/*
             2
           /   \
          3     6
         / \
        8   5
           /
          7
*/
    Node1* root1 = newNode(2);
    root1->left1 = newNode(3);
    root1->right1 = newNode(6);
    root1->left1->left1 = newNode(8);
    root1->left1->right1 = newNode(5);
    root1->left1->right1->left1 = newNode(7);

    int level1 = -1;
    if (isSorted1(root1, level1) == true)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

출력 결과

Yes

복잡도 분석

시간 복잡도: O(n) — 트리의 모든 노드를 각각 한 번씩 방문합니다.
공간 복잡도: O(n) — 최악의 경우 큐에 트리의 거의 모든 노드가 저장될 수 있습니다.