1138. Postorder Traversal (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1138

大概描述:

前序加中序求后序第一个值

特征词:

树的遍历

使用语言:

C++

解题思想:

主要是进行单项递归从而减少不必要的时间浪费,对于最终的解必然是中序遍历的第一个或者第二个

题目得分:

22

提交次数:

2

时间

64分钟

代码

#include<cstdio>
#include<vector>
using namespace std;
vector<int> pre,in;
void seekz(int pres,int pree,int ins,int ine){
 //printf("%d %d %d %d\n",pres,pree,ins,ine);
 int i = 0;
 if(ine == 0){
 printf("%d",in[0]);
 return ;
 }
 if(ine == -1){
 printf("%d",in[1]);
 return ;
 }
 while(pre[pres] != in[i])
 i++;
 seekz(pres + 1,pres + i,ins,i - 1);

}
int main(){
 int num;
 int a;
 scanf("%d",&num);
 int i = 0;
 for(;i < num;i++){
 scanf("%d",&a);
 pre.push_back(a);
 }
 for(i = 0;i < num;i++){
 scanf("%d",&a);
 in.push_back(a);
 }
 seekz(0,num - 1,0,num - 1);


}

运行结果

22

 成长

这一题使用的是中序遍历加前序求后序第一个主要注意时间,关于遍历主要记住函数名就能写出来

void seekz(int pres,int pree,int ins,int ine)

因为我发现我忘记了很多,有些地方需要加强

发表评论

电子邮件地址不会被公开。 必填项已用*标注