C++에서 트리가 동형인지 아닌지 확인

이진 트리에서 각 노드는 두 개의 자식, 즉 왼쪽 자식과 오른쪽 자식을 포함합니다. 두 개의 이진 트리가 있고 작업이 트리 중 하나를 왼쪽으로 뒤집어 다른 트리를 대칭 이동하여 얻을 수 있는지 확인하는 작업이라고 가정해 보겠습니다.

다른 나무를 왼쪽으로 뒤집어 얻을 수 있는 경우 나무는 동형입니다.

예를 들어

입력-1

<강한>

출력: 동형

설명: 주어진 Tree-2는 Tree-1을 왼쪽으로 뒤집어서 얻을 수 있으므로 Tree는 동형입니다.

이 문제를 해결하기 위한 접근 방식

이 특정 문제를 해결하기 위한 재귀적 접근 방식은 부울 함수가 두 트리의 루트 노드를 확인하는 것입니다. 두 트리의 루트가 비어 있거나 NULL이면 True를 반환하고 두 루트에 동일한 데이터가 있는지 재귀적으로 확인합니다. 그런 다음 트리의 왼쪽 및 오른쪽 노드를 재귀적으로 확인합니다.

• 두 개의 이진 트리에 대한 노드를 생성합니다.
• 부울 함수 isIsomorphicTree(node*r1, node*r2)는 두 트리의 루트를 취하고 트리가 동형인지 여부를 반환합니다.
• 처음에 트리가 비어 있거나 노드가 없으면 True를 반환합니다.
• 루트된 하위 트리가 뒤집히지 않고 둘 다 뒤집힌 경우 True를 반환합니다.

예

#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 isIsomorphicTree(treenode * r1, treenode * r2) {
   if (r1 == NULL and r2 == NULL) {
      return true;
   }
   if (r1 == NULL or r2 == NULL) {
      return false;
   }
   return (r1 -> data == r2 -> data &amp;&amp; ((isIsomorphicTree(r1 -> left, r2 -> right) &amp;&amp;       isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) &amp;&amp; isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
   struct treenode * r1 = createNode(1);
   r1 -> left = createNode(2);
   r1 -> right = createNode(3);
   r1 -> left -> left = createNode(4);
   r1 -> left -> right = createNode(5);
   r1 -> right -> left = createNode(6);
   r1 -> left -> right -> left = createNode(7);
   r1 -> left -> right -> right = createNode(8);
   struct treenode * r2 = createNode(1);
   r2 -> left = createNode(3);
   r2 -> right = createNode(2);
   r2 -> right -> left = createNode(4);
   r2 -> right -> right = createNode(5);
   r2 -> left -> right = createNode(6);
   r2 -> right -> right -> left = createNode(8);
   r2 -> right -> right -> right = createNode(7);
   if (isIsomorphicTree(r1, r2)) {
      cout << "Isomorphic" << endl;
   } else {
      cout << "Not an Isomorphic" << endl;
   }
   return 0;
}

위의 코드를 실행하면 출력이 다음과 같이 생성됩니다.

출력

Isomorphic

설명: 주어진 나무는 왼쪽으로 다른 나무를 뒤집어서 얻을 수 있으므로 동형입니다.