PKU 2255 Tree Recovery

http://poj.org/problem?id=2255
preorder、inorderで木のノードが渡される。
これをpostorderに直せというような問題。

しばらく分からなかったけれど開いて考えて、やっと分かりました。
preorderはrootが先頭に来ているので、それを元にinorderでの左右が分かるということになかなか気づけませんでした。

string pre,in;
void dfs(int ps,int pe,int is,int ie){
  for(int p=is;p<ie;++p){
    if(in[p]==pre[ps]){
      dfs(ps+1,ps+p-is+1,is,p);
      dfs(ps+p-is+1,pe,p+1,ie);
      cout<<in[p];
      return;
    }
  }
}

main(){
  while(cin>>pre>>in){
    dfs(0,SZ(pre),0,SZ(in));
    cout<<endl;
  }
}