TIOJ 1108 - 樹的三兄弟

http://tioj.infor.org/problems/1108

有點煩的一題 遞迴處理
因為可以想到 在前序中的第一個字會是樹根
然後中序中 樹根會剛好把左右邊兩顆子樹分開
所以遞迴找根就好了

覺得沒有板的code好短好可愛(?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<bits/stdc++.h> using namespace std; string _(string pre,string in){ // cout<<"pre="<<pre<<", in="<<in<<endl; assert(pre.length()==in.length()); if(pre.length()<=1)return pre; int in_pos=in.find(pre[0]); string left_pre = pre.substr(1,in_pos); string right_pre = pre.substr(in_pos+1,pre.length()-in_pos-1); string left_in = in.substr(0,in_pos); string right_in = in.substr(in_pos+1,pre.length()-in_pos-1); // cout<<left_in<<" "<<right_in<<endl; return _(left_pre,left_in)+_(right_pre,right_in)+pre[0]; } int main(){ string pre,in; while(cin>>pre>>in){ string ans = _(pre,in); cout<<ans<<endl; } }