题意 给定以中序和后序排列遍历这棵树的值，让你推导出先序遍历的值； 分析 ok，本体其实是非常简单有难度的一道题，首先，后序排列的最后一位肯定是这棵树的根节点，由此我们可以使用这个根节点来将原树拆分成两个树 然后库库拆 把每次拆的根输出就是先序排列 是不是很难理解 但是没有关系！ 举个例子 这张图是一个树！它的中序排列是什么呢？ 没错 是 DBEAFCG ！ 那么后序排列是什么呢？ 没错就是 DEBFGCA ！ 根据上面的分析 我们可以知道在后序排列的最后一位 就是这棵树的根节点！ 那就是 A ！ 现在 我们来拆！ 通过这个A 我们可以把DBEAFCG 拆成 DBE 和 FCG 两棵子树 但是后序排列的最后一位不是这两棵子树的根，该怎么办呢？ 没错！竟然是后序，那么在这个中序排列中 在后序排列里靠后的肯定是根节点！ 可以写两个for循环 一个从后往前遍历后序排列的树！ 另外一个从前往后遍历中序排列的子树！ 这时我们就可以找到 DBE 的根节点就是 B 而FCG的根节点就是 C 那我们再拆 拆成 D E F G 四棵只有一个节点的树，那么这时我们还需要拆吗？ 显然是！不需要的！ 那就在每次递归之前特判 如果 左边界 = 右边界 那就直接输出 不需要进行拆分！ 那递归该怎么写呢？ 这么写 非常简单 接下来放出AC代码：

#include<bits/stdc++.h> using namespace std; void f(string a,string b){ int len=a.size(); if(len==0){ return ; } int pos=a.find(b[len-1]); cout<<b[len-1]; f(a.substr(0,pos),b.substr(0,pos)); f(a.substr(pos+1,len-pos-1),b.substr(pos,len-pos-1)); } int main(){ string a,b; cin>>a>>b; f(a,b); return 0; }

首先，一点基本常识，给你一个后序遍历，那么最后一个就是根（如 ABCDABCDABCD ，则根为 DDD ）。 因为题目求先序，意味着要不断找根。 那么我们来看这道题方法：（示例） 中序 ACGDBHZKXACGDBHZKXACGDBHZKX ，后序 CDGAHXKZBCDGAHXKZBCDGAHXKZB ，首先可找到主根 BBB ； 那么我们找到中序遍历中的 BBB ，由这种遍历的性质，可将中序遍历分为 ACGDACGDACGD 和 HZKXHZKXHZKX 两棵子树， 那么对应可找到后序遍历 CDGACDGACDGA 和 HXKZHXKZHXKZ （从头找即可） 从而问题就变成求 111 .中序遍历 ACGDACGDACGD ，后序遍历 CDGACDGACDGA 的树 222 .中序遍历 HZKXHZKXHZKX ，后序遍历 HXKZHXKZHXKZ 的树； 接着递归，按照原先方法，找到 111 .子根 AAA ，再分为两棵子树 222 .子根 ZZZ ，再分为两棵子树。 就按这样一直做下去（先输出根，再递归）； 模板概括为 step1step1step1 :找到根并输出 step2step2step2 :将中序，后序各分为左右两棵子树； step3step3step3 :递归，重复 step1step1step1 , 222 ；

方法：不重构二叉树，直接输出前序排列 在某些大佬思路中，他们用二叉链表作存储结构重构二叉树，在通过对其进行先序遍历输出先序排列。但重构这一步其实是多余的。或者说，如果要通过递归来对二叉树进行先序遍历的话，就必须要重构二叉树（使用数组或二叉链表来存储二叉树的结构）。 但是我们知道，先序遍历的遍历顺序是根结点、左子树、右子树，而子树的后序排列的末尾元素是该子树的父结点，在知道了父结点元素后，可以在中序排列中分离出该父结点的左子树和右子树。知道了左子树和右子树的两个排列后，又可以分离出左子树和右子树的根（注意：结点的子树的根为该结点的孩子结点），不断递归地执行下去，直到分离出所有的结点。 所以对于此题，更优化的思路是不重构二叉树（即不使用任何数据结构存储二叉树的结构），通过题目输入的两个排列，不断地分离出二叉树的结点、结点的左子树以及父结点的右子树，直到分离出所有的结点。 AC代码 欢迎加入团队

无注释版

构造二叉树即可 以下是AC助手修改后的代

#include<bits/stdc++.h> using namespace std; int order(string a, string b){ int len = a.size(); if(len == 0) return 0; int pos = a.find(b[len - 1]); cout << b[len - 1]; order(a.substr(0, pos), b.substr(0, pos)); order(a.substr(pos + 1, len - pos - 1), b.substr(pos, len - pos - 1)); } int main(int argc, char* argv[]){ string a, b; cin >> a >> b; order(a, b); return 0; }

#include <bits/stdc++.h> using namespace std; string a,b; void two(string a,string b) { int len=a.size(); if(len==0) return; int pos=a.find(b[len-1]); cout<<b[len-1]; two(a.substr(0,pos),b.substr(0,pos)); two(a.substr(pos+1,len-pos-1),b.substr(pos,len-pos-1)); } void work() { cin>>a>>b; two(a,b); return; } int main(){ work(); return 0; }

#include<bits/stdc++.h> using namespace std; void f(string a,string b){ int len=a.size(); if(len==0){ return ; } int pos=a.find(b[len-1]); cout<<b[len-1]; f(a.substr(0,pos),b.substr(0,pos)); f(a.substr(pos+1,len-pos-1),b.substr(pos,len-pos-1)); } int main(){ string a,b; cin>>a>>b; f(a,b); return 0; }

#include<bits/stdc++.h> using namespace std; void dfs(string s,string t){ if(s.size() == 0) return; int id = s.find(t.back()); cout << s[id]; dfs(s.substr(0, id),t.substr(0,id)); dfs(s.substr(id + 1,s.size() - id - 1),t.substr(id,s.size() - id - 1)); } int main(){ string s,t; cin >> s >> t; dfs(s,t); return 0; }