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; } }