PTA L2-004 这是二叉搜索树吗？

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

7
8 6 5 7 10 8 11

输出样例 1：

YES
5 7 6 8 11 10 8

输入样例 2：

7
8 10 11 8 6 7 5

输出样例 2：

YES
11 8 10 7 5 6 8

输入样例 3：

7
8 6 8 5 10 9 11

输出样例 3：

NO

注意：

若测试点0和3错了，检查一下左子树的代码，或者检查确定左右子树的分界点的代码尤其是分界点下标的确定。

若你交代码一会对一会不对或则段错误，检查代码中的下标是否有越界的可能。

代码（建树版）:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

struct Node
{
    int val;
    Node* lchild;
    Node* rchild;
}a[N];

int pre[N],post[N],a_id,post_id;
int flag = 1;

void init()
{
    post_id = 0;
    a_id = 0;
    
    memset(a,0,sizeof a);
    memset(post,0,sizeof post);
}

Node* build_tree(int l,int r)
{
    if(l > r) return NULL;

    Node* root = &a[a_id++];
    root->val = pre[l];
    
    int mid = l + 1;
    if(flag)//左小
    {
        //注意下标 mid <= r
        while(mid <= r && pre[mid] < pre[l]) mid++;
        for(int i = mid;i <= r;i++)//检查
            if(pre[i] < pre[l]) return NULL;
    }
    else//左大
    {
         //注意下标 mid <= r
        while(mid <= r && pre[mid] >= pre[l]) mid++;
        for(int i = mid;i <= r;i++)//检查
            if(pre[i] >= pre[l]) return NULL;
    }
    root->lchild = build_tree(l + 1,mid - 1);
    root->rchild = build_tree(mid,r);
    
    post[post_id++] = root->val;//后序遍历
    
    return root;
}

int main()
{
    int n = 0;
    scanf("%d",&n);

    for(int i = 0;i < n;i++) scanf("%d",&pre[i]);
    Node* root = build_tree(0,n - 1);
    if(post_id != n)
    {
        init();flag = 0;//左大
        root = build_tree(0,n - 1);
    }

    if(post_id == n)
    {
        puts("YES");
        for(int i = 0;i < n;i++)
            printf("%d%c",post[i],i == n - 1 ? '\n' : ' ');
    }
    else puts("NO");
    return 0;
}

代码（不建树版）：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010;

int pre[N];
vector<int> post;
bool flag = true;

void build_tree(int l,int r)
{
    if(l > r) return;

    int mid = l + 1;
    if(flag)//左小
    {
        while(mid <= r && pre[mid] < pre[l]) mid++;
        //检查
        for(int i = mid;i <= r;i++)
            if(pre[i] < pre[l]) return;

        
    }
    else//左大
    {
        while(mid <= r && pre[mid] >= pre[l]) mid++;
        //检查
        for(int i = mid;i <= r;i++)
            if(pre[i] >= pre[l]) return;
    }
    
    build_tree(l + 1,mid - 1);
    build_tree(mid,r);
    
    post.push_back(pre[l]);//后序遍历
    return ;
}

int main()
{
    int n = 0;
    scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&pre[i]);
    
    build_tree(0,n - 1);
    if(post.size() != n)
    {
        post.clear();
        flag = false;
        build_tree(0,n - 1);
    }
    if(post.size() == n)
    {
        puts("YES");
        for(int i = 0;i < post.size();i++)
            printf("%d%c",post[i],i == n - 1 ? '\n' : ' ');
    }
    else puts("NO");
    return 0;
}