【题目描述】
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
【输入】
共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。
【输出】
一行，表示树的后序遍历序列。
【输入样例】
abdec dbeac【输出样例】
debca【算法笔记】由先序和中序遍历还原二叉树：别死记下标，一张草稿纸搞定
在二叉树的题目里，“已知先序和中序，求后序”属于必考的基本功。
很多同学逻辑都懂：先序找根，中序分左右。但在写代码时，往往死在递归的下标边界计算上。到底是+1还是-1？左子树的长度怎么算？一不小心就写出个死循环。
今天结合一张手写草稿，带大家彻底理顺这个逻辑，并给出顺序存储和链式存储两种标准写法。
1. 核心思路：对着草稿推下标
看先序a b d e c和中序d b e a c。
先序第一个
a是根。去中序里找到
a的位置，它左边的d b e是左子树，右边的c是右子树。
难点在于：如何在先序序列里，把左子树那一段精准地“抠”出来？
关键变量定义
我们在递归函数dfs(la,ra,lb,rb)中定义：
la,ra：当前子树在先序中的起点和终点。
lb,rb：当前子树在中序中的起点和终点。
root：根节点在中序里的下标（用 string 的 find 找到）。
必考逻辑（请理解并背诵）
左子树有多长？
看中序序列，从 lb 开始到 root 前面。
所以，左子树长度 (len) = root - lb。
(这一步算错，后面全错)
左子树的范围（递归左儿子）
中序：很明显是
[lb, root-1]。先序：起点是根的下一个
la+1。终点是起点加上长度。也就是：
[la+1, la+root-lb]。
右子树的范围（递归右儿子）
中序：很明显是
[root+1, rb]。先序：紧接着左子树后面。
起点：左子树终点 + 1。也就是
la+(root-lb)+1。终点：直接就是
ra。
2. 方法一：顺序存储（完全二叉树思维）
利用完全二叉树性质：节点k的左儿子下标是2*k，右儿子是2*k+1。
优点：逻辑简单。
缺点：极其浪费空间。如果是“歪脖子树”（退化成链），空间复杂度是 2^N。除非确定节点少或者满二叉树，否则慎用。
//先建树 再后序遍历输出 //方法一：顺序存储 //特点：利用2*k和2*k+1计算位置 #include<bits/stdc++.h> using namespace std; string a,b;//先序遍历 中序遍历 struct node{ int l;//记录左儿子节点的下标 int r;//记录右儿子节点的下标 char data; node(){ l=r=0; } }tre[4000];//顺序存储一定要开大数组，防止越界 void postorder(int root){//后序输出 if(tre[root].l!=0) postorder(root*2); if(tre[root].r!=0) postorder(root*2+1); cout<<tre[root].data; } void dfs(int la,int ra,int lb,int rb,int k){ //k代表所建树中根节点的下标 la ra代表本次先序遍历的起点终点 //lb rb代表本次中序遍历的起点终点 if(la>ra||lb>rb) return; int root=b.find(a[la]);//找到根节点在中序遍历输出中的位置 tre[k].data=a[la];//顺序存储记录根节点的数据 if(root>lb){//代表有左子树 tre[k].l=2*k;//顺序存储的特点 //左子树长度=root-lb，所以先序终点=la+(root-lb) dfs(la+1,la+root-lb,lb,root-1,k*2); } if(root<rb){//代表有右子树 tre[k].r=2*k+1;//顺序存储的特点 //右子树先序起点=la+左子树长度+1 dfs(la+root-lb+1,ra,root+1,rb,2*k+1); } } int main(){ cin>>a>>b; int ra=a.size(); int rb=b.size(); dfs(0,ra-1,0,rb-1,1); postorder(1); return 0; }3. 方法二：链式存储（静态数组模拟）
打比赛最推荐的写法。
不依赖 2*k，而是用一个全局计数器 ind，用一个申请一个。哪怕树退化成一条链（世代单传二叉树），空间复杂度也只是 O(N)。
原理：每次
++ind给新节点发一个“身份证号”，父节点把这个号码记在l或r里。
//方法二：链式存储（静态数组池） //特点：空间利用率高，通用性强 #include<bits/stdc++.h> using namespace std; string a,b; struct node{ int l; int r; char data; node(){l=r=0;} }tre[1000]; int ind=1;//链式存储存放结点位置 void postorder(int root){ if(tre[root].l!=0) postorder(tre[root].l); if(tre[root].r!=0) postorder(tre[root].r); cout<<tre[root].data; } void dfs(int la,int ra,int lb,int rb,int k){ int root=b.find(a[la]);//找到根节点在b中的位置下标 tre[k].data=a[la]; if(root>lb){//如果左子树存在 tre[k].l=++ind;//链式存储的特点：申请新节点 dfs(la+1,la+root-lb,lb,root-1,ind); } if(root<rb){//代表右子树存在 tre[k].r=++ind;//链式存储的特点：申请新节点 dfs(root-lb+la+1,ra,root+1,rb,ind); } } int main(){ cin>>a>>b; int ra=a.size()-1; int rb=b.size()-1; dfs(0,ra,0,rb,1); postorder(1); return 0; }4. 避坑总结
关于下标：千万别死记
la+root-lb这种一长串的东西。考试时像我一样在草稿纸上画一段，算出左子树长度，然后根据“起点+长度”去推，绝对不会错。关于存储：
如果是平时练习或者题目保证是完全二叉树 ->用方法一（写得快）。
如果是正式比赛或者不确定树的形状 ->必用方法二（稳，不爆内存）。
关于代码风格：大家注意看，我在顺序存储里也保留了
tre[k].l=2*k。虽然这一步可以通过计算省略，但加上去之后，它和链式存储的逻辑就完全统一了，非常适合理解“二叉树的本质”。
