题解 P1305 【新二叉树】

我觉得题解不少人写得比较复杂，这个题目总的来说要点有三个： ①构造二叉树，这里需要注意的是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 } ```