二叉树遍历(flist)（信息学奥赛一本通- P1364）全网最易理解版本

【题目描述】

【输入】

【输出】

【输入样例】

DBEAC ABCDE

【输出样例】

ABDEC

【算法笔记】已知中序和层序，怎么求先序？(两种解法详解)

0. 前言

在二叉树遍历的题目中，我们最常见的是“前序+中序”或者“后序+中序”求树。这种题目比较简单，因为根节点总是躲在字符串的最头或者最尾，一抓一个准。

但是，“中序 + 层序” 往往让人头大。

因为层序遍历是按层级从上往下数的，子树的根节点在字符串里是散落的，不像前序/后序那样连续。

今天就来拆解这道经典题目，采用“建树求解”和“直接递归”两种解法。

1. 核心逻辑：谁是根？

不管用哪种写法，破解这道题的核心逻辑只有一句话：

层序遍历负责“选老大”（定根节点），中序遍历负责“分地盘”（划分子树）。

• 层序遍历 (Level Order)：这是一张“权力排行榜”。不管这棵树长什么样，排在层序遍历前面的节点，辈分一定比后面的高。

• 中序遍历 (In Order)：这是一张“座位表”。根节点坐中间，左子树的所有节点都在它左边，右子树的所有节点都在它右边。

解题三部曲：

1. 查榜：拿着层序遍历的名单，去中序遍历的当前范围内找。谁在层序里出现得最早，谁就是当前的根。

2. 分家：找到了根，中序遍历就被切成了两半——左边是左子树，右边是右子树。

3. 递归：对左右两半重复上述过程。

2. 解法一：正规建树法

如果你不仅需要输出先序遍历，后续还需要对这就棵树进行其他操作（比如求高度、镜像翻转），那么老老实实把树建起来是最稳妥的。

思路解析

1. 开一个结构体数组tre[]存树，用cnt动态分配节点编号。

2. 写一个build(L, R, u)函数：

   • L, R：代表当前处理的是中序字符串a的[L, R]这一段。

   • u：代表当前节点的编号。

3. 在build内部找到根节点位置pos后：

   • 递归build(L, pos-1, ...)去填tre[u].l(左孩子)。

   • 递归build(pos+1, R, ...)去填tre[u].r(右孩子)。

4. 最后写一个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. 解法二：直接输出法

如果题目仅仅要求输出先序遍历，不需要后续操作，那我们完全可以省去建树的过程。

思路解析

先序遍历的顺序是：根 -> 左 -> 右。

我们完全可以利用递归函数的执行顺序来模拟这个过程：

1. 在函数里找到根。

2. 直接cout这个根。

3. 递归调用函数处理左边。

4. 递归调用函数处理右边。

这种写法不需要结构体，不需要数组，代码极短，是考场上的拿分利器。

//第二种做法 不建树 直接输出 #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; }