数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究找到 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!
更新于：2021 年 3 月 12 日
155 次浏览
广告