问题遇到的现象和发生背景
天梯杯模拟赛L2-3题 只拿了17分
问题相关代码,请勿粘贴截图
//ÀËÂþ²àÓ°
#include<iostream>
#include<map>
using namespace std;
int n;
int mid[10000];
int last[10000];
int max_len=0;
map<int,int> v[10000];
typedef struct tree{
int data;
int i;
int deep;
tree* left;
tree* right;
};
tree* create(int m_i,int l_i,int range){
tree* t = (tree*)malloc(sizeof(tree));
if(range<=0)return NULL;
t->data=last[l_i];
int r_l=0;
for(r_l=0;m_i+r_l<range;r_l++){
if(mid[m_i+r_l]==t->data)break;
}
int r_r=range-r_l-1;
t->left=create(m_i,l_i-r_r-1,r_l);
t->right=create(m_i+r_l+1,l_i-1,r_r);
return t;
}
void get_i(tree* t,int d,int i){
if(t){
t->deep=d;
//第d层索引为i的值为t->data
v[d][i]=t->data;
if(d>max_len)max_len=d;
t->i=i;
get_i(t->left,d+1,i*2);
get_i(t->right,d+1,i*2+1);
}
return;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>mid[i];
}
for(int i=0;i<n;i++){
cin>>last[i];
}
if(n==0){
return 0;
}
tree* root=create(0,n-1,n);
get_i(root,1,1);
//´òÓ¡ÓÒ±ß
// printf("R:");
// p_r(root);
// printf("\nL:");
// p_l(root);
// p_l(root);
//ÀÏ°æ±¾17·Ö´úÂë
printf("R:");
map<int,int>::iterator it;
for(int i=1;;i++){
if(v[i].size()>0){
it=v[i].end();
it--;
printf(" %d",it->second);
}else{
break;
}
}
printf("\n");
printf("L:");
for(int i=1;;i++){
if(v[i].size()>0){
it=v[i].begin();
printf(" %d",it->second);
}else{
break;
}
}
return 0;
}