（信息学奥赛一本通- P1364）全网最易理解版本)
【题目描述】
树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。
【输入】
两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。
【输出】
一行，表示二叉树的先序序列。
【输入样例】
DBEAC ABCDE【输出样例】
ABDEC【算法笔记】已知中序和层序，怎么求先序？(两种解法详解)
0. 前言
在二叉树遍历的题目中，我们最常见的是“前序+中序”或者“后序+中序”求树。这种题目比较简单，因为根节点总是躲在字符串的最头或者最尾，一抓一个准。
但是，“中序 + 层序” 往往让人头大。
因为层序遍历是按层级从上往下数的，子树的根节点在字符串里是散落的，不像前序/后序那样连续。
今天就来拆解这道经典题目，采用“建树求解”和“直接递归”两种解法。
1. 核心逻辑：谁是根？
不管用哪种写法，破解这道题的核心逻辑只有一句话：
层序遍历负责“选老大”（定根节点），中序遍历负责“分地盘”（划分子树）。
层序遍历 (Level Order)：这是一张“权力排行榜”。不管这棵树长什么样，排在层序遍历前面的节点，辈分一定比后面的高。
中序遍历 (In Order)：这是一张“座位表”。根节点坐中间，左子树的所有节点都在它左边，右子树的所有节点都在它右边。
解题三部曲：
查榜：拿着层序遍历的名单，去中序遍历的当前范围内找。谁在层序里出现得最早，谁就是当前的根。
分家：找到了根，中序遍历就被切成了两半——左边是左子树，右边是右子树。
递归：对左右两半重复上述过程。
2. 解法一：正规建树法
如果你不仅需要输出先序遍历，后续还需要对这就棵树进行其他操作（比如求高度、镜像翻转），那么老老实实把树建起来是最稳妥的。
思路解析
开一个结构体数组
tre[]存树，用cnt动态分配节点编号。写一个
build(L, R, u)函数：L, R：代表当前处理的是中序字符串
a的[L, R]这一段。u：代表当前节点的编号。
在
build内部找到根节点位置pos后：递归
build(L, pos-1, ...)去填tre[u].l(左孩子)。递归
build(pos+1, R, ...)去填tre[u].r(右孩子)。
最后写一个
preorder函数把树打印出来。
//第一种做法 建树然后遍历 #include <iostream> #include <string> using namespace std; string a,b;//中序 层序 int cnt=1;//节点计数器,从1号开始分配 struct node{ char data;//存字母 int l,r;//存左孩子和右孩子的下标编号 }tre[1005]; //L,R:当前范围下标,u:当前节点编号 void build(int L,int R,int u){ int pos=-1;//用来存根节点在a中的下标 //遍历层序b,谁排在前面谁就是根 for(int i=0;i<b.length();i++){ int k=a.find(b[i]); //必须在当前范围[L,R]里才算数 if(k>=L&&k<=R){ tre[u].data=b[i];//确定根 pos=k;//记下位置 break; } } //处理左子树 if(pos>L){ cnt++; tre[u].l=cnt; build(L,pos-1,cnt);//递归左边[L,pos-1] }else{ tre[u].l=0; } //处理右子树 if(pos<R){ cnt++; tre[u].r=cnt; build(pos+1,R,cnt);//递归右边[pos+1,R] }else{ tre[u].r=0; } } //先序遍历输出 void preorder(int u){ if(u==0)return; cout<<tre[u].data; preorder(tre[u].l); preorder(tre[u].r); } int main(){ cin>>a>>b; build(0,a.size()-1,1); preorder(1); return 0; }3. 解法二：直接输出法
如果题目仅仅要求输出先序遍历，不需要后续操作，那我们完全可以省去建树的过程。
思路解析
先序遍历的顺序是：根 -> 左 -> 右。
我们完全可以利用递归函数的执行顺序来模拟这个过程：
在函数里找到根。
直接
cout这个根。递归调用函数处理左边。
递归调用函数处理右边。
这种写法不需要结构体，不需要数组，代码极短，是考场上的拿分利器。
//第二种做法 不建树 直接输出 #include <iostream> #include <string> using namespace std; string a,b;//中序 层序 //L为左边界下标 R为右边界下标 void dfs(int L,int R){ //如果左手跑到右手右边去了,说明范围空了,不干了 if(L>R)return; int k; //拿着层序字符串(b)里的名字,一个一个去查 for(int i=0;i<b.size();i++){ int pos=a.find(b[i]);//算出b[i]在中序的位置 //只要这个位置在我们当前的范围[L,R]里面,它就是根 if(pos>=L&&pos<=R){ k=pos;//记下位置,等会用来切分 cout<<b[i];//先序遍历直接打印根 break;//找到了最大的,停 } } //递归处理左右两边 dfs(L,k-1);//处理k左边的 dfs(k+1,R);//处理k右边的 } int main(){ cin>>a>>b; //一开始的范围是:从0到最后一个 dfs(0,a.size()-1); return 0; }4. 总结与避坑
哪个更好？
写法二（直接输出）：代码量少，逻辑清晰，不容易写错，推荐考试使用。
写法一（建树）：更通用。如果题目下一问是让你求树的深度，或者求后序遍历，写法一改动更小。
常见坑点
在 for 循环找根的时候，千万不要找到一个 a.find(b[i]) 存在的就直接 break！
一定要加上 if (k >= L && k <= R) 这个判断。
因为 b 里的节点可能在 a 的其他部分（比如已经在上一层的递归中被处理过了），我们只关心当前这个子树范围内的节点。
代码总结：
/* //第一种做法 建树然后遍历 #include <iostream> #include <string> using namespace std; string a,b;//中序 层序 int cnt=1;//节点计数器,从1号开始分配 struct node{ char data;//存字母 int l,r;//存左孩子和右孩子的下标编号 }tre[1005]; //L,R:当前范围下标,u:当前节点编号 void build(int L,int R,int u){ int pos=-1;//用来存根节点在a中的下标 //遍历层序b,谁排在前面谁就是根 for(int i=0;i<b.length();i++){ int k=a.find(b[i]); //必须在当前范围[L,R]里才算数 if(k>=L&&k<=R){ tre[u].data=b[i];//确定根 pos=k;//记下位置 break; } } //处理左子树 if(pos>L){ cnt++; tre[u].l=cnt; build(L,pos-1,cnt);//递归左边[L,pos-1] }else{ tre[u].l=0; } //处理右子树 if(pos<R){ cnt++; tre[u].r=cnt; build(pos+1,R,cnt);//递归右边[pos+1,R] }else{ tre[u].r=0; } } //先序遍历输出 void preorder(int u){ if(u==0)return; cout<<tre[u].data; preorder(tre[u].l); preorder(tre[u].r); } int main(){ cin>>a>>b; build(0,a.size()-1,1); preorder(1); return 0; } */ //第二种做法 不建树 直接输出 #include <iostream> #include <string> using namespace std; string a,b;//中序 层序 //L为左边界下标 R为右边界下标 void dfs(int L,int R){ //如果左手跑到右手右边去了,说明范围空了,不干了 if(L>R)return; int k; //拿着层序字符串(b)里的名字,一个一个去查 for(int i=0;i<b.size();i++){ int pos=a.find(b[i]);//算出b[i]在中序的位置 //只要这个位置在我们当前的范围[L,R]里面,它就是根 if(pos>=L&&pos<=R){ k=pos;//记下位置,等会用来切分 cout<<b[i];//先序遍历直接打印根 break;//找到了最大的,停 } } //递归处理左右两边 dfs(L,k-1);//处理k左边的 dfs(k+1,R);//处理k右边的 } int main(){ cin>>a>>b; //一开始的范围是:从0到最后一个 dfs(0,a.size()-1); return 0; }
