PAT甲级1043题（判断二叉搜索树）

二叉树题

PAT

发布日期: 2021-02-24

文章字数: 275

阅读时长: 1 分

阅读次数:

1.题目介绍

1043

2.考察点，难度

二叉树类，二叉树遍历，难度中

3.解题代码

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
int preorder[N],postorder[N],inorder[N],idx;

bool build(int il,int ir,int pl, int pr, int type){

    if(il>ir)   return true;
    int root = preorder[pl];
    int i;
    if(type==0){
        for(i=il;i<=ir;i++)
            if(inorder[i]==root)
                break;
        if(i>ir)    return false;
    }else{
        for(i=ir;i>=il;i--)
            if(inorder[i]==root)
                break;
        if(i<il)    return false;
    }
    bool res=true;
    if(!build(il,i-1,pl+1,pl+1+i-1+il,type)) res= false;
    if(!build(i+1,ir,pl+1+i-1-il+1,pr,type))  res=false;
    postorder[idx++]=root;
    return res;
}

int main(){

    int n;
    cin>>n;
    for(int i=0;i<n;i++)    {
        cin>>preorder[i];
        inorder[i]=preorder[i];
    }
    sort(inorder,inorder+n);
    if(build(0,n-1,0,n-1,0)){
        puts("YES");
        cout<<postorder[0];
        for(int i=1;i<n;i++)    cout<<" "<<postorder[i];
        cout<<endl;
    }else{
        reverse(inorder,inorder+n);
        idx = 0;
        if (build(0, n - 1, 0, n - 1, 1))
        {
            puts("YES");
            cout << postorder[0];
            for (int i = 1; i < n; i ++ ) cout << ' ' << postorder[i];
            cout << endl;
        }
        else puts("NO");
    }
    return 0;
}