C++ 코딩테스트 강좌, 트리의 부모 찾기

문제 설명

주어진 이진 트리에서 각 노드의 부모 노드를 찾는 프로그램을 작성하세요. 이진 트리의 노드는 숫자로 레이블이 붙어 있으며, 다음과 같은 구조로 정의됩니다:


    struct Node {
        int value;
        Node* left;
        Node* right;
        
        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };

입력으로는 노드의 리스트와 요청된 노드의 값이 주어집니다. 출력으로는 해당 노드의 부모 노드의 값이 출력되어야 하며, 부모 노드가 없는 경우에는 -1을 반환해야 합니다.

예시

문제 접근 방식

문제를 해결하기 위해 이진 트리를 탐색하여 각 노드의 부모를 파악하는 방법을 사용할 것입니다. 우리는 다음과 같은 과정을 따릅니다:

트리의 루트 노드를 시작점으로 설정합니다.
큐를 사용하여 BFS(너비 우선 탐색) 방식으로 트리의 노드를 탐색합니다.
각 노드를 확인하고 요청된 노드의 부모를 저장합니다.
요청된 노드를 찾으면 해당 부모 노드를 출력합니다.

코드 구현


    #include 
    #include 
    #include 
    using namespace std;

    struct Node {
        int value;
        Node* left;
        Node* right;

        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };

    Node* buildTree(const vector>& nodes) {
        unordered_map nodeMap;
        for (const auto& p : nodes) {
            int child = p.first;
            int parent = p.second;

            if (nodeMap.find(child) == nodeMap.end())
                nodeMap[child] = new Node(child);

            if (parent != -1) {
                if (nodeMap.find(parent) == nodeMap.end())
                    nodeMap[parent] = new Node(parent);

                if (!nodeMap[parent]->left)
                    nodeMap[parent]->left = nodeMap[child];
                else
                    nodeMap[parent]->right = nodeMap[child];
            }
        }
        return nodeMap.begin()->second; // 첫번째로 추가된 노드를 루트로 반환
    }

    int findParent(Node* root, int target) {
        if (!root) return -1;

        queue q;
        q.push(root);
        Node* parent = nullptr;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Node* current = q.front();
                q.pop();
                
                if (current->left) {
                    if (current->left->value == target) {
                        return current->value;
                    }
                    q.push(current->left);
                }

                if (current->right) {
                    if (current->right->value == target) {
                        return current->value;
                    }
                    q.push(current->right);
                }
            }
        }
        
        return -1; // 부모를 찾지 못한 경우
    }

    int main() {
        // 트리 구성: (child, parent)
        vector> nodes = {{2, 1}, {7, 3}, {6, 4}, {5, -1}};

        Node* root = buildTree(nodes); // 트리 빌드
        int target = 3; // 요청 노드
        int parentValue = findParent(root, target);

        cout << parentValue << endl; // 부모 출력

        return 0;
    }

코드 설명

위 코드는 이진 트리를 만들고 요청된 노드의 부모를 찾는 전반적인 과정을 보여줍니다.

buildTree: 주어진 (child, parent) 리스트를 사용하여 트리를 구성하는 함수입니다. 각 노드를 맵에 저장하여 부모-자식 관계를 설정합니다.
findParent: BFS를 사용하여 요청된 값의 부모를 찾는 함수입니다. 각 노드를 탐색하면서 자식 노드가 요청된 값과 같으면 현재 노드의 값을 반환합니다.
main: 프로그램의 진입점으로, 샘플 입력을 통해 트리를 빌드하고 부모를 찾습니다.

종합 정리

이 문제는 이진 트리의 기본 구조를 이해하고, 자료구조를 효과적으로 활용하는 방법을 배우는 데 유익합니다. BFS를 통해 노드를 탐색하며 부모 노드를 찾는 과정은 실무에서도 많이 사용되는 접근 방법입니다. 각 단계별로 주의를 기울여야 하며, 예외 처리를 통해 문제를 예방할 수 있습니다.

추가 문제

이 문제의 변형으로, 특정 노드의 자식 노드들을 찾는 문제나, 트리의 깊이를 구하는 문제 등을 고려할 수 있습니다. 다양한 변형 문제를 통해 트리에 대한 이해를 더욱 깊게 할 수 있습니다.

팁 및 주의사항

재귀를 사용할 때는 무한 루프에 빠지지 않도록 주의해야 합니다.
노드의 부모가 없는 경우를 처리하기 위한 조건을 명확히 설정해야 합니다.
트리의 구조에 따라 알고리즘의 성능이 달라질 수 있으니, 다양한 경우를 실험해보세요.