https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192
#include<iostream> #include<queue> using namespace std; int a[30+10],b[30+10],l[30+10],r[30+10],aans[30+10],pos=0; queue <int> ans; void bt(int x1,int y1,int x2,int y2){ if(x1==y1) return ; if(x2==y2) return ; int root=a[y1]; int i; for(i=x2;i<=y2;i++) if(b[i]==root) break; if(i>x2){ l[y1]=i-x2-1+x1; bt(x1,i-x2-1+x1,x2,i-1); } if(i<y2){ r[y1]=y1-1; bt(i-x2+x1,y1-1,i+1,y2); } } int main(){ for(int i=0;i<30+10;i++){ l[i]=-1; r[i]=-1; } int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; bt(0,n-1,0,n-1); /*for(int i=0;i<n;i++) cout<<i<<" "<<a[i]<<" "<<l[a[i]]<<" "<<r[a[i]]<<endl;*/ ans.push(n-1); while(!ans.empty()){ int t=ans.front(); aans[pos++]=t; ans.pop(); if(l[t]!=-1) ans.push(l[t]); if(r[t]!=-1) ans.push(r[t]); } for(int i=0;i<pos-1;i++) cout<<a[aans[i]]<<" "; cout<<a[aans[pos-1]]<<endl; return 0; }
我傻了,一开始直接用l和r数组存的键值(因为看了刘汝佳的紫书的那道题),结果俩点不过,后来把l和r换成存下标就过了???
也许是因为键值很大???