資料結構
網路
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 次瀏覽
廣告