给出一棵二叉树的中序与后序排列。求出它的先序排列。约定树结点用不同的大写字母表示且二叉树的节点个数 ≤8。输入格式共两行均为大写字母组成的字符串表示一棵二叉树的中序与后序排列。输出格式共一行一个字符串表示一棵二叉树的先序。输入输出样例输入 #1复制BADC BDCA输出 #1复制ABCD说明/提示【题目来源】NOIP 2001 普及组第三题我相信只要是学过离散数学的对二叉树非常熟悉我们简单回顾一下拿题目例子来举令m为中序遍历l为后序遍历l的最后一个就是根root然后看中序遍历可以把BADC分成左右左B右DC再看后序遍历得C是根最后得到先序遍历。所以我采用递归的方法更容易理解和想到#includebits/stdc.husing namespace std;void buildtree(string m,string l){if(m.empty()){return ;}char rootl[l.size()-1];coutroot;int posm.find(root);string left_mm.substr(0,pos);string right_mm.substr(pos1);int lenleft_m.size();string left_ll.substr(0,len);string right_ll.substr(len,l.size()-len-1);buildtree(left_m,left_l);buildtree(right_m,right_l);}int main(){ios::sync_with_stdio(false);cin.tie(0);string m,l;cinml;buildtree(m,l);return 0;}
