C++のバイナリツリーで特定のノードのミラーを検索します

この問題では、二分木が与えられます。私たちのタスクは、バイナリツリーで特定のノードのミラーを見つけることです。ノードが与えられ、反対側のサブツリーでそのノードの鏡像を見つけます。

問題を理解するために例を見てみましょう

入力

出力

mirror of B is E.

ソリューションアプローチ

この問題を解決する簡単な解決策の1つは、左のサブツリーと右のサブツリーに2つのポインターを使用して、ルートからの再帰を使用することです。次に、ターゲット値について、ミラーが見つかった場合はミラーを返し、それ以外の場合は他のノードを繰り返します。

ソリューションの動作を説明するプログラム

例

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