原题目
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度\(\le 8\)）
输入格式
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
1行，表示一棵二叉树的先序。
解题思路
初步思路
-
定义node结构体表示树结点，定义node类型的tree[]数组来存储树； -
通过递归的方式根据树的中序和后序序列来
确定访问这棵树； -
最后用再对存储好的树访问其先序序列。
进一步考虑
-
对于中序序列与后序序列的下标范围一下子好难找到他们线性的关系，因此全部当作函数参数来传。
-
由于本题递归的过程就是从树的根节点向下，先访问左子树再访问右子树，与先序遍历的访问次序相同，因此可以在考虑结点时直接将结点输出，免去了先存储树再先序遍历的步骤。
简易版代码
#include<bits/stdc++.h>
using namespace std;
string mid,last;
int len;
void dfs(int ml,int mr,int ll,int lr)//ml,mr定位中序序列，ll,lr定位后序序列
{
cout<<last[lr];
int i;
for(i=0;i<=len;i++)if(mid[i]==last[lr])break;//从中序序列中找到根结点位置
if(i>ml)dfs(ml,i-1,ll,lr-mr+i-1);//两序列下标的范围是重点
if(i<mr)dfs(i+1,mr,ll+i-ml,lr-1);//要很仔细地去模拟
}
int main()
{
cin>>mid;
cin>>last;
len=mid.length()-1;
dfs(0,len,0,len);
return 0;
}
总结与反思
二叉树有关的题目多为模拟题，因此需要超级无敌非常细心，并思考能否简化算法，这样才能不掉坑。