树的同构[天梯赛二叉树专项训练]

本文主要是介绍树的同构[天梯赛二叉树专项训练]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目描述
思路
AC代码

题目描述

在这里插入图片描述

输入样例1
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
输出样例1
Yes输入样例2
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
输出样例2
No

思路

1.用结构体数组模拟二叉树–由于题目中给定节点值均不相同，因此这种方法可取
2.建树时，存储每棵树的根节点，后序判断是否同构时，从根节点开始判断
3.Compare函数判断两棵树是否同构
①当前两棵树均为空树–同构
②一棵树为空，一棵树不为空–不同构
③两棵树均不为空，但是值不相同–不同构
④除上述三种特殊情况外，进一步递归判断第一棵树和第二棵树的左右孩子是否相同或交叉相等

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef struct node
{char data;int left, right;
}node;
node tree1[N], tree2[N];
bool vis[N];
bool Judge_Num(char x)
{return x >= '0' && x <= '9';
}
int Init(node t[])
{int n;char root, l, r;cin >> n;if(!n) return -1;memset(vis, false, sizeof(vis));for(int i = 0; i < n; i ++){cin >> root >> l >> r;//cout << root << " " << l << " " << r << endl;t[i].data = root;if(Judge_Num(l)){int x = l - '0';t[i].left = x;vis[x] = true;}else t[i].left = -1;if(Judge_Num(r)){int x = r - '0';t[i].right = x;vis[x] = true;}else t[i].right = -1;}for(int i = 0; i < n; i ++){if(!vis[i]) return i;}
}bool Compare(int root1, int root2)
{if(root1 == -1 && root2 == -1) return true;if((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) return false;if(tree1[root1].data != tree2[root2].data) return false;return (Compare(tree1[root1].left, tree2[root2].left) && Compare(tree1[root1].right, tree2[root2].right))|| (Compare(tree1[root1].left, tree2[root2].right) && Compare(tree1[root1].right, tree2[root2].left)); 
}
int main()
{int root1 = Init(tree1);int root2 = Init(tree2);if(Compare(root1, root2)) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}