UOA1001: Binary Tree Intersection And Union
何故か知らないけど最近解いてる人が多いので、便乗してみました。二分木の和と積を求める問題。
人によってコード長の差が激しいのを見て、できるだけ簡単な実装を考えてから書いてみました。十分縮まったので満足です。
与えられた木を別個に作らず、1つ目の木に2つ目の木を上書きするのがポイント。あるノードを訪れるたびにそのノードのカウンタを増やしていくと、そのノードが和・積に含まれるかどうかはカウンタを見るだけで判断できる。
#include <iostream> using namespace std; const int nil=-1; const int N=256; struct node{ int c,l,r; node(){c=0;l=r=nil;} } v[N]; int cnt; void parse(string& s,int &n,int r){ v[r].c++; n++; if(s[n]!=','){ if(v[r].l==nil) v[r].l=++cnt; parse(s,n,v[r].l); } n++; if(s[n]!=')'){ if(v[r].r==nil) v[r].r=++cnt; parse(s,n,v[r].r); } n++; } string str(int r,int n){ if(v[r].c<n) return ""; return "("+(v[r].l!=nil?str(v[r].l,n):"")+","+(v[r].r!=nil?str(v[r].r,n):"")+")"; } main(){ char op; string a,b; while(cin >> op >> a >> b){ for(int i=0;i<N;++i) v[i]=node(); cnt=0; int n; parse(a,n=0,0); parse(b,n=0,0); cout << str(0,op=='i' ? 2 : 1) << endl; } }
そういえば、UOAのSubmit数がついに10,000に達したようで。おめでとうございます。