69 lines
1.6 KiB
C++
69 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1e6 + 10;
|
||
|
||
//树的结构体+存储数组
|
||
//此处：为二叉树的标准创建、遍历模板，可用于其它试题！
|
||
struct Node {
|
||
int id; // 当前结点ID
|
||
int left; // 左结点ID
|
||
int right; // 右结点ID
|
||
char value; //当前结点的value值(本题中未使用)
|
||
} t[N];
|
||
|
||
//前序遍历
|
||
void pre_order(Node node) {
|
||
//利用递归前序输出二叉树
|
||
if (node.id) {
|
||
cout << node.value;
|
||
pre_order(t[node.left]);
|
||
pre_order(t[node.right]);
|
||
}
|
||
}
|
||
|
||
int n;
|
||
|
||
/**
|
||
测试用例：
|
||
6
|
||
abc
|
||
bdi
|
||
cj*
|
||
d**
|
||
i**
|
||
j**
|
||
|
||
参考答案：abdicj
|
||
*/
|
||
int b[N];
|
||
|
||
int main() {
|
||
cin >> n; //二叉树的结点数量
|
||
//读入每个结点及它的左右儿子
|
||
for (int i = 1; i <= n; i++) {
|
||
string str;
|
||
cin >> str;
|
||
int j = str[0] - 'a' + 1;//结点编号
|
||
b[j]++;//没有父亲的才是根
|
||
//结点编号
|
||
t[j].id = j;
|
||
//记录字母值
|
||
t[j].value=str[0];
|
||
//记录左儿子
|
||
if (str[1] != '*') t[j].left = str[1] - 'a' + 1, b[t[j].left]++;;
|
||
//记录右儿子
|
||
if (str[2] != '*') t[j].right = str[2] - 'a' + 1, b[t[j].right]++;;
|
||
}
|
||
//第一次提交，30分，似乎要求通过运算找到根，第一个输入的未必是根
|
||
//第二次，记录谁是根，AC。
|
||
int root;
|
||
for (int i = 1; i <= 26; i++)
|
||
if (b[i] == 1) {
|
||
root = i;
|
||
break;
|
||
}
|
||
//前序遍历
|
||
pre_order(t[root]);
|
||
return 0;
|
||
} |