树 - 树的同构

题目

链接：https://pintia.cn/problem-sets/15/problems/711

// 判断树的同构
#include<iostream>
#include<vector>
using namespace std;

struct node {
	char ch;
	int left, right;
};
vector<node> v1, v2;     //递归减少参数传递

int Get(vector<node>& v)
{
	char c, l, r;
	int n,root=-1;      //初始化空节点
	scanf("%d\n", &n);
	v.resize(n);
	vector<int> hash(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%c %c %c", &c, &l, &r);
		getchar();       //注意字符接收
		v[i].ch = c;
		if (l != '-')
		{
			v[i].left = l - '0';
			hash[l - '0'] = 1;
		}
		else v[i].left = -1;
		if (r != '-')
		{
			v[i].right = r - '0';
			hash[r - '0'] = 1;
		}
		else v[i].right = -1;
	}
	for (int i = 0; i < n; i++)
	{
		if (hash[i] == 0)
		{
			root = i;
			break;
		}
	}
	return root;
}

bool dfs(int root1, int root2)
{
	if (root1 == -1 && root2 == -1) return true;
	if ((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) return false;
	if (v1[root1].ch != v2[root2].ch) return false;
	bool lhs = true, rhs = true;
	lhs = dfs(v1[root1].left, v2[root2].left);
	if (lhs)
		rhs = dfs(v1[root1].right, v2[root2].right);
	else
	{
		lhs = dfs(v1[root1].left, v2[root2].right);
		rhs = dfs(v1[root1].right, v2[root2].left);
	}
	return lhs && rhs;
}

int main()
{
	int root1,root2;
	root1 = Get(v1);
	root2 = Get(v2);
	bool ans = false;
	ans = dfs(root1, root2);
	if (ans) printf("Yes");
	else printf("No");
	return 0;
}