一、前序、中序遍历求后序遍历
输入
6
1 2 3 4 5 6
3 2 4 1 6 5
输出
3 4 2 6 5 1
way1
存入前序遍历和前序遍历中每个数对应的位置
存入中序遍历的数
solve(1,n)
void solve(引入所求范围l,r)
{
if(范围中只有一个数)
存入后序
for循环找出中序范围内前序遍历数最靠前的,这个数是这个子树的根节点
判断左右的子树继续递归
把这个根节点存入last后序遍历中
}
#include<iostream>
#include<string>
#include<stack>
using namespace std;
const int maxn=105;
int pre[maxn],in[maxn],last[maxn],position[maxn];
int n,cnt=0;
void solve(int l,int r)
{
if(l==r)
{
last[++cnt]=in[l];
return;
}
int xh=1e5,wz;
for(int i=l;i<=r;i++)
{
if(position[in[i]]<xh)
{
xh=position[in[i]];
wz=i;
}
}
if(wz-1>=l) solve(l,wz-1);
if(wz+1<=r) solve(wz+1,r);
last[++cnt]=in[wz];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>pre[i];
position[pre[i]]=i;
}
for(int i=1;i<=n;i++)
{
cin>>in[i];
}
solve(1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",last[i]);
}
}
way2
先把前序存入pre,中序存入in
- solve中的形参
- prel 当前子树的根节点位置
- inl当前中序的起始位置
- lastl当前后序的起始位置
如果n==1,说明这个点是叶节点,直接存入**last[lastl]**处即可
#include<iostream>
#include<string>
#include<stack>
using namespace std;
const int maxn=105;
int pre[maxn],in[maxn],last[maxn],n,cnt=0;
//参数:PreL为当前前序序列的起始位置,即根节点位置
//InL为当前中序序列中的左或右子树的起始位置
//LastL为后序序列中子序列起始位置的下标
//n为当前左或右子树的长度
void solve(int prel,int inl,int lastl,int n)
{
if(n==0) return;
if(n==1)
{
last[lastl]=pre[prel];
return;
}
int root=pre[prel];//当前这棵树的根节点位置
last[lastl+n-1]=root;//起始位置+总长-1就是最后的位置
int i;
for(i=1;i<=n;i++)
{
if(in[inl+i]==root)
break;
}
int l=i,r=n-i-1;
solve(prel+1,inl,lastl,l);
solve(prel+l+1,inl+l+1,lastl+l,r);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>pre[i];
}
for(int i=1;i<=n;i++)
{
cin>>in[i];
}
solve(1,1,1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",last[i]);
}
}
03-树3 Tree Traversals Again (25 分)(前中序变后序)
二、中序、后序遍历求前序遍历
输入
6
3 2 4 1 6 5
3 4 2 6 5 1
输出
1 2 3 4 5 6
way1
#include<iostream>
#include<string>
#include<stack>
using namespace std;
const int maxn=105;
int pre[maxn],in[maxn],last[maxn],position[maxn],n,cnt=0;
void solve(int l,int r)
{
if(l==r)
{
pre[++cnt]=in[l];
return;
}
int xh=0,wz;
for(int i=l;i<=r;i++)
{
if(position[in[i]]>xh)
{
xh=position[in[i]];
wz=i;
}
}
pre[++cnt]=in[wz];
if(wz-1>=l) solve(l,wz-1);
if(wz+1<=r) solve(wz+1,r);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>in[i];
}
for(int i=1;i<=n;i++)
{
cin>>last[i];
position[last[i]]=i;
}
solve(1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",pre[i]);
}
}