数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中判断两棵树是否同构
在二叉树中，每个节点包含两个子节点，即左子节点和右子节点。假设我们有两棵二叉树，任务是检查其中一棵树是否可以通过翻转另一棵树的左侧来获得。
如果一棵树可以通过翻转另一棵树的左侧来获得，则称这两棵树是同构的。
例如
输入-1
输出：同构
解释：给定的树-2可以通过翻转树-1的左侧获得，因此这两棵树是同构的。
解决此问题的方法
解决此特定问题的递归方法是，一个布尔函数将检查两棵树的根节点。如果两棵树的根节点都为空或为 NULL，则返回 True，并递归检查两个根节点的数据是否相同。然后，我们将递归检查树的左节点和右节点。
- 为两棵二叉树创建节点。
- 布尔函数 isIsomorphicTree(node*r1, node*r2) 获取两棵树的根节点，并返回树是否同构。
- 最初，如果树为空或没有任何节点，则返回 True。
- 如果根节点的子树没有翻转，并且如果两者都翻转，则返回 True。
示例
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
if (r1 == NULL and r2 == NULL) {
return true;
}
if (r1 == NULL or r2 == NULL) {
return false;
}
return (r1 -> data == r2 -> data && ((isIsomorphicTree(r1 -> left, r2 -> right) && isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) && isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
struct treenode * r1 = createNode(1);
r1 -> left = createNode(2);
r1 -> right = createNode(3);
r1 -> left -> left = createNode(4);
r1 -> left -> right = createNode(5);
r1 -> right -> left = createNode(6);
r1 -> left -> right -> left = createNode(7);
r1 -> left -> right -> right = createNode(8);
struct treenode * r2 = createNode(1);
r2 -> left = createNode(3);
r2 -> right = createNode(2);
r2 -> right -> left = createNode(4);
r2 -> right -> right = createNode(5);
r2 -> left -> right = createNode(6);
r2 -> right -> right -> left = createNode(8);
r2 -> right -> right -> right = createNode(7);
if (isIsomorphicTree(r1, r2)) {
cout << "Isomorphic" << endl;
} else {
cout << "Not an Isomorphic" << endl;
}
return 0;
}运行以上代码将生成以下输出：
输出
Isomorphic
解释：给定的树可以通过翻转另一棵树的左侧获得，因此它是同构的。
更新于： 2021年2月23日
299 次查看
广告