C++로 중위 순회(inorder) 방식으로 완전 이진 트리의 미러 이미지 노드 합 구하기

이 문제에서는 완전 이진 트리(Complete Binary Tree)가 주어지며, 우리의 목표는 이 트리를 중위 순회(inorder traversal) 방식으로 탐색하면서 각 노드와 그 노드의 미러 이미지(거울상) 노드 값의 합을 구하는 프로그램을 작성하는 것입니다.

즉, 왼쪽 서브트리를 중위 순회하면서 각 노드마다 대칭 위치에 있는 노드의 값을 함께 더해야 합니다. 예를 들어 왼쪽 리프 노드를 방문하고 있다면, 그 노드의 미러 이미지인 오른쪽 리프 노드의 값을 더하는 식입니다.

핵심 개념 정리

완전 이진 트리(Complete Binary Tree)란 마지막 레벨을 제외한 모든 레벨이 최대 개수의 노드를 가지고, 마지막 레벨의 노드들은 왼쪽부터 차례대로 채워져 있는 이진 트리를 말합니다.

중위 순회(Inorder Traversal)는 왼쪽 서브트리를 먼저 방문한 뒤 루트를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 트리 순회 기법입니다.

예제로 문제 이해하기

입력

출력 − 9 9 17 2

설명 − 왼쪽 서브트리의 중위 순회 결과는 5 → 7 → 8 → 1 입니다. 각 노드에 미러 이미지 노드의 값을 더하면 다음과 같습니다.

5 + 4 = 9
7 + 2 = 9
8 + 9 = 17
1 + 1 = 2

접근 방법

이 문제는 중위 순회 방식으로 트리를 탐색하여 해결할 수 있습니다. 핵심은 두 개의 노드 포인터를 동시에 사용하는 것인데, 하나는 왼쪽 서브트리를 탐색하고 다른 하나는 그 노드의 미러 이미지를 방문합니다. 예를 들어 왼쪽 서브트리의 루트 노드에 대응되는 mirrorroot가 그 노드의 거울상 위치를 함께 탐색하도록 하는 방식입니다.

C++ 구현 예제

다음은 솔루션의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;
typedef struct node {
   int data;
   struct node* left;
   struct node* right;
   node(int d){
      data = d;
      left = NULL;
      right = NULL;
   }
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
   if (root->left == NULL && rootMirror->right == NULL)
      return;
   printMirrorSum(root->left, rootMirror->right);
   cout<<(root->left->data + rootMirror->right->data)<<endl;
   printMirrorSum(root->right, rootMirror->left);
}
int main(){
   Node* root = new Node(1);
   root->left = new Node(7);
   root->right = new Node(2);
   root->left->left = new Node(5);
   root->left->right = new Node(8);
   root->right->left = new Node(9);
   root->right->right = new Node(4);
   cout<<"노드와 미러 이미지 노드의 합 :\n";
   printMirrorSum(root, root);
   if (root)
      cout<<(root->data + root->data);
   return 0;
}

실행 결과

노드와 미러 이미지 노드의 합 :
9
9
17
2