目的:根据先序和中序,给出后序遍历的第一个节点。
输入:
N <= 50000 结点数字
先序序列
中序序列
输出:
后序序列的第一个数字。
算法:
后序遍历的第一个点,是最左下方的点。
若当前点有左子树,那么就在左子树中找第一个点。如果没有左子树,就在右子树中找。如果左右子树都没有,则当前点就是找到的点。
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> preorder,inorder;
int n;
void findfirstkey(int prel,int prer,int inl,int inr)
{
if(prel==prer)
{
printf("%d",preorder[prel]);
return;
}
int k = preorder[prel];
int u = -1;
for(int i=inl;i<=inr;i++)
{
if(k == inorder[i])
{
u = i;
break;
}
}
int leftnum = u-inl;
if(leftnum!=0)
{
findfirstkey(prel+1,prel+leftnum,inl,inl+leftnum-1);
}else
{
findfirstkey(prel+1,prer,inl+1,inr);
}
}
int main()
{
scanf("%d",&n);
preorder.resize(n);
for(int i=0;i<n;i++)
{
scanf("%d",&preorder[i]);
}
inorder.resize(n);
for(int i=0;i<n;i++)
{
scanf("%d",&inorder[i]);
}
findfirstkey(0,n-1,0,n-1);
return 0;
}
反思:
有些手生