Tree : Top View

이진 트리의 "상단 뷰"를 찾는 문제입니다. 상단 뷰란 이진 트리를 위에서 아래로 내려다 볼 때, 가장 왼쪽 노드부터 가장 오른쪽 노드까지 순서대로 보이는 노드들의 값을 출력하는 것을 의미합니다.

 

상단 뷰를 찾기 위해서는 이진 트리의 루트 노드에서 시작하여 왼쪽으로 이동할 때는 왼쪽 자식 노드로, 오른쪽으로 이동할 때는 오른쪽 자식 노드로 이동하면서 노드들의 값을 출력해야 합니다. 이 때, 같은 수평 레벨에 여러 노드가 있는 경우에는 가장 왼쪽 노드를 출력해야 합니다.

 

문제의 목표는 주어진 이진 트리에서 상단 뷰에 있는 노드들의 값을 순서대로 출력하는 것

 

 

BFS(Breadth-First Search) 알고리즘을 사용하여 풀 수 있습니다.

BFS를 사용하면 각 노드의 수평 거리를 추적할 수 있으며, 각 수평 거리에 대해 가장 먼저 방문한 노드만을 출력할 수 있습니다. 이를 통해 상단 뷰를 효율적으로 찾을 수 있습니다.

// 이진 트리 노드 정의
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int data) : data(data), left(nullptr), right(nullptr) {}
};

// 상단 뷰 출력 함수
void topView(Node* root) {
    if (root == nullptr) {
        return;
    }

    std::queue<std::pair<Node*, int>> q; // 노드와 수평 거리를 저장하는 큐
    std::map<int, int> topViewMap;       // 수평 거리와 값을 저장하는 맵

    q.push({root, 0}); // 루트 노드의 거리는 0

    while (!q.empty()) {
        Node* current = q.front().first;
        int horizontalDistance = q.front().second;
        q.pop();

        // 현재 거리에 해당하는 값이 맵에 없으면 추가
        if (topViewMap.find(horizontalDistance) == topViewMap.end()) {
            topViewMap[horizontalDistance] = current->data;
        }

        // 왼쪽 자식 노드 큐에 추가 (거리를 1 줄임)
        if (current->left) {
            q.push({current->left, horizontalDistance - 1});
        }

        // 오른쪽 자식 노드 큐에 추가 (거리를 1 증가)
        if (current->right) {
            q.push({current->right, horizontalDistance + 1});
        }
    }

    // 수평 거리에 따라 상단 뷰 출력
    for (const auto& entry : topViewMap) {
        std::cout << entry.second << " ";
    }
    std::cout << std::endl;
}

C++에서 std::map은 STL(Standard Template Library)의 일부로, 키-값(key-value) 쌍을 저장하는 연관 컨테이너

std::map은 레드-블랙 트리(red-black tree)로 구현되어 있어, 삽입과 삭제 연산에도 균형을 유지하면서 빠른 속도를 제공

std::map은 키와 값의 쌍을 저장하며, 키를 통해 값을 검색할 수 있습니다.

 

std::map::find(key)는 주어진 키(key)를 검색하여 해당 키를 가진 요소(iterator)를 반환합니다. 만약 해당 키를 찾지 못하면 std::map::end()를 반환

 

topViewMap에 해당 거리의 값을 가진 노드가 존재하지 않을 때만 실행되며, 중복된 거리의 값을 방지하기 위한 용도로 사용