题解 P1305 【新二叉树】
teafrogsf
2017-06-08 16:55:15
我觉得题解不少人写得比较复杂,这个题目总的来说要点有三个:
①构造二叉树,这里需要注意的是n的范围没有给出,我一开始以为26个字母只会出现一次就只弄了100的数组,但结果就爆了,所以我开了10000,对于这个题目来说常数可以了;
②三四行的前序遍历
③洛谷专属(但其实好像是Linux评测系统?)输入格式,吞换行字符不能只getchar,这里建议C/C++党用C++的getline,会快一些(毕竟string类方便)
然后就是代码
```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define f(i,a,b) for(i=a;i<=b;++i)
using std::cin;
using std::string;//不太建议using namespace std
int n;
char a[10010];
string s;
void preorder(int i)
{
if(a[i]==0)return;
if(a[i]!='*')printf("%c",a[i]);
preorder(i<<1);//位运算,表示i*2,下面表示i*2+1,这样快一些
preorder(i<<1|1);
}
int main()
{
int i,j;
scanf("%d",&n);
string instead;
getline(cin,instead);//吞换行
getline(cin,s);//第一个直接进去
a[1]=s[0],a[2]=s[1],a[3]=s[2];
f(i,2,n)
{
getline(cin,s);
f(j,1,10000)if(a[j]==s[0])a[j<<1]=s[1],a[j<<1|1]=s[2];//拼常数
}
preorder(1);//根节点1
}
```