【题解-信息学奥赛一本通】1339：【例3-4】求后序遍历

题目1339【例3-4】求后序遍历题目描述输入一棵二叉树的先序和中序遍历序列输出其后序遍历序列。输入共两行第一行一个字符串表示树的先序遍历第二行一个字符串表示树的中序遍历。树的结点一律用小写字母表示。输出一行表示树的后序遍历序列。时空限制1s / 64MB样例输入abdec dbeac样例输出debca代码#includebits/stdc.husingnamespacestd;string pre,mid;voiddfs(intprel,intprer,intmidl,intmidr){intmidrootmid.find(pre[prel]);//在中序遍历序列中根的位置if(midrootmidl)dfs(prel1,prelmidroot-midl,midl,midroot-1);//左子树if(midrootmidr)dfs(prelmidroot-midl1,prer,midroot1,midr);//右子树coutpre[prel];//根}intmain(){cinpremid;dfs(0,pre.size()-1,0,mid.size()-1);return0;}结果