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

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 이진 트리에서 주어진 노드의 미러를 찾는 것입니다. 노드가 주어지고 반대쪽 하위 트리에서 해당 노드의 미러 이미지를 찾습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

출력

mirror of B is E.

솔루션 접근 방식

문제를 해결하는 한 가지 간단한 솔루션은 왼쪽 하위 트리와 오른쪽 하위 트리에 대해 두 개의 포인터를 사용하여 루트에서 재귀를 사용하는 것입니다. 그런 다음 미러가 발견되면 대상 값에 대해 미러를 반환하고 그렇지 않으면 다른 노드를 반복합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#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;
   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!