PAT A1043 Is It a Binary Search Tree

题目链接

解题思路

首先根据输入数据构建一棵二叉排序树，然后分别用vector存放其先序遍历、后序遍历、镜像先序遍历、镜像后序遍历。使用vector的好处是可以直接比较！然后把初始数据和先序遍历和镜像先序遍历比较，如果相等就对应输出对应后续遍历！

注意

1、自定义结构体记得加上构造函数。

2、树的镜像遍历可以直接将遍历左右子树的前后顺序改变一下，改成先r->right,再r->left。

代码

#include <cstdio>
#include <vector>
using namespace std;
const int maxn=1010;
int n;
vector<int> nums;
struct Node{
    int data;
    Node* left;
    Node* right;
    Node(int d=0,Node* l=NULL,Node* r=NULL):data(d),left(l),right(r){}
};
Node* root=NULL;
void insert(Node* &r,int x){
    if(r==NULL) {
        r=new Node(x);
        return;//要记得返回啊
    }
    if(r->data>x){
        insert(r->left,x);
    }else{
        insert(r->right,x);
    }
}
Node* build(){
    Node* r=NULL;
    for(int i=0;i<n;i++){
        insert(r,nums[i]);
    }
    return r;
}
void preOrder(Node* r,vector<int>& v){
    if (r==NULL) return;
    v.push_back(r->data);
    preOrder(r->left,v);
    preOrder(r->right,v);
}
void postOrder(Node* r,vector<int>& v){
    if(r==NULL) return;
    postOrder(r->left,v);
    postOrder(r->right,v);
    v.push_back(r->data);
}
void preMorder(Node* r,vector<int>& v){
    if(r==NULL) return;
    v.push_back(r->data);
    preMorder(r->right,v);
    preMorder(r->left,v);
}
void postMorder(Node* r,vector<int>& v){
    if(r==NULL) return;
    postMorder(r->right,v);
    postMorder(r->left,v);
    v.push_back(r->data);
}
int main(){
    scanf("%d",&n);
    int x;
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        nums.push_back(x);
    }
    root=build();
    vector<int> pre,post,preM,postM;
    preOrder(root,pre);
    preMorder(root,preM);
    if(nums==pre) {
        printf("YES\n");
        postOrder(root,post);
        for(int i=0;i<n;i++){
            if (i!=0) printf(" ");
            printf("%d",post[i]);
        }
    }else if(nums==preM){
        printf("YES\n");
        postMorder(root,postM);
        for(int i=0;i<n;i++){
            if (i!=0) printf(" ");
            printf("%d",postM[i]);
        }
    }else{
        printf("NO\n");
    }
    return 0;
}