C++의 대칭 트리

이진 트리가 있고 작업이 자체 대칭을 구성하는지 여부를 확인하는 것이라고 가정해 보겠습니다. 대칭 이진 트리는 자신의 거울 이미지를 구성합니다.

예를 들어

입력-1:

<강한>

출력:

True

설명:

주어진 이진 트리는 자신의 미러 이미지를 구성하므로 출력은 True입니다.

입력-2:

<강한>

출력:

False

설명:

주어진 이진 트리는 자신의 거울 이미지를 만들지 않기 때문에 대칭이 아닙니다.

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

대칭 이진 트리는 자신의 거울 이미지인 트리이므로 트리의 왼쪽 노드와 오른쪽 노드가 동일한지 여부를 확인해야 합니다.

부울 함수는 처음에 왼쪽 노드와 오른쪽 노드를 확인합니다. 노드가 비어 있거나 NULL이면 True를 반환합니다. 다른 경우에는 왼쪽 또는 오른쪽 자식이 있는지 확인한 다음 대칭 트리가 되도록 동일해야 합니다.

• 루트와 그 자식을 포함하는 이진 트리를 가져옵니다.
• 부울 도우미 함수 도우미(node*root1, node*root2)는 왼쪽 자식과 오른쪽 자식이 같은지 여부를 확인하는 데 도움이 되는 동일한 트리의 두 루트를 사용합니다.
• 트리가 비어 있거나 NULL이면 True를 반환합니다.
• 트리의 왼쪽 노드와 오른쪽 노드가 같은지 여부를 재귀적으로 확인합니다.
• 위의 모든 조건이 충족되지 않으면 False를 반환합니다.

예시

#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로 출력됩니다.