C++로 이진 트리의 대칭 여부 확인하기

이진 트리가 주어졌을 때, 해당 트리가 자기 자신의 대칭 구조를 이루는지 확인하는 것이 과제입니다. 대칭 이진 트리(Symmetric Binary Tree)란 자기 자신의 거울상(mirror image)을 만드는 트리를 의미합니다.

예시

입력-1:

출력:

True

설명:

주어진 이진 트리가 자기 자신의 거울상을 이루므로 출력은 True입니다.

입력-2:

출력:

False

설명:

주어진 이진 트리가 자기 자신의 거울상을 만들지 않으므로 대칭 트리가 아닙니다.

문제 해결 접근 방법

대칭 이진 트리는 자기 자신이 거울상을 이루는 트리입니다. 즉, 트리의 왼쪽 부분과 오른쪽 부분이 서로 동일한 구조와 값을 가지는지 확인해야 합니다.

불리언(Boolean) 함수는 먼저 왼쪽 노드와 오른쪽 노드를 검사합니다. 두 노드가 모두 비어 있거나(NULL) 없다면 True를 반환합니다. 그 외의 경우에는 양쪽 자식 노드의 값이 서로 같은지 확인하며, 모든 노드에서 이 조건이 성립해야 대칭 트리가 됩니다.

알고리즘 단계

• 루트와 그 자식 노드들을 포함하는 이진 트리를 준비합니다.
• 불리언 헬퍼 함수 helper(node* root1, node* root2)는 같은 트리의 두 루트를 인자로 받아 왼쪽 자식과 오른쪽 자식이 동일한지 검사합니다.
• 트리가 비어 있거나 NULL이면 True를 반환합니다.
• 재귀적으로 트리의 왼쪽 노드와 오른쪽 노드가 서로 같은지 확인합니다.
• 위의 어떤 조건도 만족하지 않으면 False를 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
bool helper(struct treenode * root1, struct treenode * root2) {
   if (root1 == NULL and root2 == NULL)
      return true;
   if (root1 and root2 and root1 -> data == root2 -> data)
      return (helper(root1 -> left, root2 -> right) and helper(root1 -> right, root2 -> left));
   return false;
}
bool isSymmetry(struct treenode * root) {
   return helper(root, root);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   if (isSymmetry(root)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

False

설명:

예제에서 사용된 트리는 좌우 대칭 구조가 아니므로 최종 출력은 False가 됩니다. 이처럼 재귀적 헬퍼 함수를 활용하면 트리의 대칭 여부를 간단하고 효율적으로 판별할 수 있습니다.