题意分析

给两棵树，判断是否相同，注意结点可能字母是相同的。

解题思路

由于有结点可能字母相同，就变得麻烦了，以第2颗树的每个结点作为根去建树，在比较两棵树是否相同，对于每个结点的情况，利用map进行映射。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 128;
 
int T;
struct Tree {
	int cnt;
	char node[N];
	vector<int> g[N];
	void clear() {
		cnt = 0;
		memset(node, 0, sizeof(node));
		memset(g, 0, sizeof(g));
	}
}T1, T2;
map<vector<int>, int> vis;
 
int read(Tree &T, int fa) {
	int x = T.cnt++;
	if (fa >= 0) T.g[x].push_back(fa);
	char c;
	scanf(" %c %c", &T.node[x], &c);
	if (c != '(') {
		ungetc(c, stdin);
		return x;
	}
	while (1) {
		T.g[x].push_back(read(T, x));
		if (scanf("%c", &c) != 1 || c != ',') break;
	}
	return x;
}
 
int solve(Tree T, int u, int fa) {
	vector<int> vi;
	if (fa < 0) {
		for (int i = 0; i < T.g[u].size();i ++) {
			int v = T.g[u][i];
			if (v == fa) continue;
			vi.push_back(solve(T, v, u));
		}
		int best = 0;
		int m = vi.size();
		for (int s = 1; s < m; s++) {
			for (int i = best, j = s, k = 0; k < m; k++) {
				if (vi[i] != vi[j]) {
					if (vi[j] < vi[i]) best = s;
					break;
				}
				if (++i >= m) i = 0;
				if (++j >= m) j = 0;
			}
		}
		rotate(vi.begin(), vi.begin() + best, vi.end());
	}
	else {
		int i;
		for (i = 0; T.g[u][i] != fa; i++);
		while (1) {
			if (++i >= T.g[u].size()) i = 0;
			int v = T.g[u][i];
			if (v == fa) break;
			vi.push_back(solve(T, v, u));
		}
	}
	vi.push_back(T.node[u]);
	int k;
	if (vis.count(vi))
		k = vis[vi];
	else {
		k = vis.size();
		vis[vi] = k;
	}
	return k;
}
 
bool judge() {
	if (T1.cnt != T2.cnt) return false;
	vis.clear();
	for (int i = 0; i < T1.cnt; i++)
		if (solve(T1, i, -1) == solve(T2, 0, -1)) return true;
		return false;
}
 
int main() {
	scanf("%d", &T);
	while (T--) {
		T1.clear(); T2.clear();
		read(T1, -1); read(T2, -1);
		printf("%s\n", judge()?"same":"different");
	}
	return 0;
}