ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือค้นหามิเรอร์ของโหนดที่กำหนดในทรีไบนารี เราจะได้รับโหนด และค้นหาภาพสะท้อนของโหนดนั้นในทรีย่อยตรงข้าม
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
ผลลัพธ์
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!
