#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 26;

int parent[N],lchild[N],rchild[N];

void pre(int root)
{
	printf("%c",root + 'a');
	if(lchild[root] != -1) pre(lchild[root]);
	if(rchild[root] != -1) pre(rchild[root]);
}

int main()
{
	int n;
	scanf("%d",&n);
	
	memset(parent,-1,sizeof(parent));
	memset(lchild,-1,sizeof(lchild));
	memset(rchild,-1,sizeof(rchild));
	
	while(n--)
	{
		getchar();
		char p,l,r;
		scanf("%c%c%c",&p,&l,&r);
		
		if(l != '*') lchild[p-'a'] = l - 'a',parent[l-'a'] = p - 'a';
		if(r != '*') rchild[p-'a'] = r - 'a',parent[r-'a'] = p - 'a';
	}
	
	int root;
	for(int i=0;i<26;i++) if(parent[i] == -1 && !(lchild[i] == -1 && rchild[i] == -1)) root = i;
	
	pre(root);
	
	return 0;
}

我用的方法当然是比较朴实的方法，但我自己电脑上没问题，提交了却RE就很迷惑，还请各位大牛帮忙看下