PAT-A1043 Is It a Binary Search Tree (25 分)/不建树的DFS/市面最简洁之一

╰半夏微凉° 2023-05-29 02:55 5阅读 0赞

A1043题目地址：[https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856][https_pintia.cn_problem-sets_994805342720868352_problems_994805440976633856]

是之前好几道不建树版DFS求后序序列（A1086、A1138）的变型。

参考了liuchuo的代码：[https://www.liuchuo.net/archives/2153][https_www.liuchuo.net_archives_2153]

其中的这段代码还能更加精简：

getpost(0, n - 1);
        if(post.size() != n) {
            isMirror = true;
            post.clear();
            getpost(0, n - 1);
        }

其实用下面这一行就能判断题目给的是BST还是BST的mirror了：

if(pre[0]>pre[1])dfs(0,n-1,true);//是BST
        else dfs(0,n-1,false);//是BST-mirror

整道题的AC代码如下：

#include<iostream>
    #include<vector>
    using namespace std;
    int n,pre[1005];
    vector<int> post;
    void dfs(int s,int e,bool flag){
        int i=s+1,j=e;
        if(flag){
            while(i<=e && pre[s]>pre[i])i++;
            while(j>s && pre[s]<=pre[j])j--;
        }else{
            while(i<=e && pre[s]<=pre[i])i++;
            while(j>s && pre[s]>pre[j])j--;
        }
        if(i-j!=1)return;
        dfs(s+1,j,flag);
        dfs(i,e,flag);
        post.push_back(pre[s]);
    }
    int main(){
        cin>>n;
        for(int i=0;i<n;i++)cin>>pre[i];
        if(pre[0]>pre[1])dfs(0,n-1,true);
        else dfs(0,n-1,false);
        if(post.size()!=n)cout<<"NO"<<endl;
        else{
            cout<<"YES"<<endl<<post[0];
            for(int i=1;i<n;i++)cout<<" "<<post[i];
        }
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70][]

[https_pintia.cn_problem-sets_994805342720868352_problems_994805440976633856]: https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856
[https_www.liuchuo.net_archives_2153]: https://www.liuchuo.net/archives/2153
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191101225036632.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw==,size_16,color_FFFFFF,t_70