【题解】P1030 求先序遍历
yummy
2020-08-15 13:06:37
这题相当经典，相信每一个二叉树入门的同学们都会做到这道题。基本解法都已经差不多了，但是我们在这里要介绍一种优化，让多数同学的 $O(N^2)$ 甚至 $O(N^3)$ 的程序变成 $O(N)$ 的。
**如果您已经会了 $O(N)$ 解法却无处测试是否真的 $O(N)$，可以到[这里](https://www.luogu.com.cn/problem/T138237)测试，但是由于暂时无人AC，不保证数据完全正确。**
首先我们放一个很普通的程序：
```cpp
#include<bits/stdc++.h>
using namespace std;
string a,b;
void tree(string inord,string aftord)//重点1
{
if(inord.size()==0)
return;
char ch=aftord[aftord.size()-1];
cout<<ch;
int k = inord.find(ch);//重点2
tree(inord.substr(0,k),aftord.substr(0,k));
tree(inord.substr(k+1),aftord.substr(k,aftord.size()-k-1));
}
int main()
{
cin>>a>>b;
tree(a,b);
return 0;
}
```
首先我们很清楚：`tree`函数无论如何实现，由于每个节点最多做一次根节点，所以最多有 $n$ 棵非空子树，所以`tree`的调用次数必然 $O(N)$，这点毋庸置疑，没有什么好优化的地方。
我们看一眼重点1，虽然`string`看起来像一个整体，传参是 $O(1)$ 的，但是实际上由 $O(N)$ 的字符数量构成的。传参总复杂度 $O(N^2)$，卡掉方法：一条链。
我们发现传入的`string`总是原串一个子串，于是我们可以只传下标。于是每次传参就是 $O(1)$ 的。
接下来看重点2，`find`看起来没有循环没有递归，加上常数确实小，也容易被认为 $O(1)$，但是本质上也是 $O(N)$。
有了上面这两个优化，每次`tree`执行都是 $O(1)$ 的，可以解决 $n\leq 10^5$ 的情况。参考代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
char a[11],b[45],c[14];
int n;
void prt(int al,int ar,int bl,int br)
{
if(al>ar)return;
int sep=c[b[br]-'A'];
putchar(a[sep]);
prt(al,sep-1,bl,sep-al+bl-1);
prt(sep+1,ar,sep-al+bl,br-1);
}
int main()
{
scanf("%s%s",a+1,b+1);
for(n=1;a[n];n++)
c[a[n]-'A']=n;
prt(1,n-1,1,n-1);
return 0;
}
```
开头那题参考代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,md[114514],bk[114514],gt[114514];
void ft(int mdl,int mdr,int bkl,int bkr)
{
if(mdl>mdr)
return;
printf("%d ",bk[bkr]);
int sep=gt[bk[bkr]];
ft(mdl,sep-1,bkl,sep-1-mdl+bkl);
ft(sep+1,mdr,sep-mdl+bkl,bkr-1);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&md[i]);
gt[md[i]]=i;
}
for(int i=1;i<=n;i++)
scanf("%d",&bk[i]);
ft(1,n,1,n);
return 0;
}
```