PTA 这是二叉搜索树吗?


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换成存下标就过了???
也许是因为键值很大???


注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告