PAT A1119 前序遍历后续遍历不唯一生成

￡神魔★判官ぃ 2022-03-07 04:16 93阅读 0赞

![clipboard.png][]

之前仅仅接触过如何通过二叉树的中序+先序/后序序列生成唯一二叉树，这一次见到了这个新的题型；

这里先梳理一个概念，之所以会生成树不唯一，一定是有一个叶子，无论其在父节点的左右子节点，都可能生成相同的先序和后序遍历序列；

所以这个时候，思路就很清晰，我们判别一个序列是否唯一，条件就是是否有一个节点只有一个子节点；

大致的序列分割和先序和后续相同，这个后面专门开一个blog进行总结；

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<vector>
    #include<set>
    #include<algorithm>
    using namespace std;
    using std::vector;
    using std::set;
    vector<int>in,pre,post;
    bool uniq=true;
    
    void chargement(int prl,int prr,int pol,int por){
        if(prl==prr){
            in.push_back(pre[prl]);
            return ;
        }
        if(pre[prl]==post[por]){
            int i=prl+1;
            while(i<=prr&&pre[i]!=post[por-1])
                i++;
            if(i-prl>1)
                chargement(prl+1,i-1,pol,pol+(i-prl-1)-1);
            else
                uniq=false;
            in.push_back(post[por]);
            chargement(i,prr,pol+(i-prl-1),por-1);
        }
    }
    
    
    int main(){
        int n;
        scanf("%d",&n);
        pre.resize(n);
        post.resize(n);
        for(int i=0;i<n;i++)
            scanf("%d",&pre[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&post[i]);
        chargement(0,n-1,0,n-1);
        printf("%s\n%d", uniq == true ? "Yes" : "No", in[0]);
        for (int i = 1; i < in.size(); i++)
            printf(" %d", in[i]);
        printf("\n");
        system("pause");
        return 0;
    }

[clipboard.png]: /images/20220307/ba994ab473a14808a56e3bd9c282225c.png