C++ 이진 트리에서 주어진 노드의 미러 노드 찾기 방법

문제 소개

이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 우리의 과제는 트리 안에서 주어진 노드의 미러(mirror) 노드를 찾는 것입니다. 즉, 특정 노드가 주어졌을 때 반대편 서브트리에서 대칭되는 위치에 있는 노드를 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

출력

B의 미러는 E입니다.

해결 접근 방식

이 문제를 해결하는 가장 간단한 방법은 루트에서부터 재귀적으로 탐색하면서, 왼쪽 서브트리와 오른쪽 서브트리를 각각 가리키는 두 개의 포인터를 함께 사용하는 것입니다. 탐색 도중 목표 값의 미러 노드를 발견하면 해당 노드의 값을 반환하고, 발견하지 못했다면 나머지 노드들을 계속 순회합니다.

알고리즘의 동작 과정을 단계별로 정리하면 다음과 같습니다.

루트가 NULL이면 0을 반환합니다.
루트 자신이 목표 노드라면 해당 값을 그대로 반환합니다.
왼쪽과 오른쪽 서브트리를 동시에 내려가며 비교합니다. 왼쪽 노드의 키가 목표 값과 같으면 오른쪽 노드의 키를, 오른쪽 노드의 키가 목표 값과 같으면 왼쪽 노드의 키를 반환합니다.
미러를 아직 찾지 못했다면 (왼쪽의 왼쪽, 오른쪽의 오른쪽) 쌍과 (왼쪽의 오른쪽, 오른쪽의 왼쪽) 쌍으로 재귀 호출을 이어갑니다.

구현 예제

다음 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

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

struct Node {
    int key;
    struct Node* left, *right;
};

struct Node* newNode(int key){
    struct Node* n = (struct Node*) malloc(sizeof(struct Node));
    if (n != NULL){
        n->key = key;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    else{
        cout << "Memory allocation failed!" << endl;
        exit(1);
    }
}

int mirrorNodeRecur(int node, struct Node* left, struct Node* right){
    if (left == NULL || right == NULL)
        return 0;
    if (left->key == node)
        return right->key;
    if (right->key == node)
        return left->key;
    int mirrorNode = mirrorNodeRecur(node, left->left, right->right);
    if (mirrorNode)
        return mirrorNode;
    return mirrorNodeRecur(node, left->right, right->left);
}

int findMirrorNodeBT(struct Node* root, int node) {
    if (root == NULL)
        return 0;
    if (root->key == node)
        return node;
    return mirrorNodeRecur(node, root->left, root->right);
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(3);
    root->left->left->left = newNode(4);
    root->left->left->right = newNode(5);
    root->right = newNode(6);
    root->right->left = newNode(7);
    root->right->right = newNode(8);

    int node = root->left->key;
    int mirrorNode = findMirrorNodeBT(root, node);
    cout << "The node is root->left, value : " << node << endl;
    if (mirrorNode)
        cout << "The Mirror of Node " << node << " in the binary tree is Node " << mirrorNode;
    else
        cout << "The Mirror of Node " << node << " in the binary tree is not present!";

    node = root->left->left->right->key;
    mirrorNode = findMirrorNodeBT(root, node);
    cout << "\n\nThe node is root->left->left->right, value : " << node << endl;
    if (mirrorNode)
        cout << "The Mirror of Node " << node << " in the binary tree is Node " << mirrorNode;
    else
        cout << "The Mirror of Node " << node << " in the binary tree is not present!";
}

실행 결과

The node is root->left, value : 2
The Mirror of Node 2 in the binary tree is Node 6

The node is root->left->left->right, value : 5
The Mirror of Node 5 in the binary tree is not present!

복잡도 분석

시간 복잡도: 최악의 경우 트리의 모든 노드를 한 번씩 방문하므로 O(N)입니다. 여기서 N은 트리의 전체 노드 수입니다.
공간 복잡도: 재귀 호출 스택이 트리의 높이(h)만큼 사용되므로 O(h)이며, 한쪽으로 치우친 편향 트리에서는 최악의 경우 O(N)까지 증가할 수 있습니다.