PAT_甲级_1119 Pre- and Post-order Traversals

乔梓鑫 发布于 2 月 26 日

题目大意

给定一棵二叉树的前序和后序序列，要求判断该树是否唯一并输出中序序列，不唯一的时候输入任意一棵树的中序序列即可

算法思路

在给定先序和后序序列后，我们只能通过先序第一个节点和后序最后一个节点相等来判断剩余的左右子树的范围，但是对于先序和后序中的左右子树的相对顺序是一致的，那么我们可以设置左子树的长度为leftSize，从0开始进行遍历，只要先序的左子树节点集合和后序的左子树节点集合相同(顺序可以不一样)，同时先序左子树的首节点和后序左子树的尾节点是相同的，这样我们就得到了一个成功的左右子树的划分，又由于我们需要判断是否有多种划分结果，在第一次获得成功划分的时候需要继续进行查找，直到获得第二次成功划分或者没有第二次划分从而退出循环。这里对建树的操作作进一步细说，

提交结果

AC代码

#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>

using namespace std;

int n;
int pre[35],post[35];
bool multiChoice = false;

struct Node{
    int v{};
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* createTree(int preL,int preR,int postL,int postR){
    if(preL>preR){
        return nullptr;
    }
    Node* root = new Node;
    root->v = pre[preL];
    // 统计当前子树划分成功的次数
    int count = 0;
    // 在左子树长度为0，判断是否可以形成右子树
    if(pre[preL+1]==post[postR-1]){
        ++count;
    }
    int leftSize = 0;
    unordered_set<int> s;
    // 遍历左子树长度
    int size = preR-preL+1;// 当前子树的长度
    for(int i=1;i<size;++i){
        s.insert(pre[preL+i]);
        s.insert(post[postL+i-1]);
        if(s.size()==i&&pre[preL+1]==post[postL+i-1]){
            // 当前划分的左子树元素满足左子树定义
            ++count;
            leftSize = i;// 记录左子树长度
            if(count>=2){
                // 存在多种划分
                multiChoice  =true;
                break;
            }
        }
    }
    // 先序：左子树范围为[preL+1,preL+leftSize],右子树范围为[preL+leftSize+1,preR]
    root->left = createTree(preL+1,preL+leftSize,postL,postL+leftSize-1);
    // 后序: 左子树范围为[postL,postL+leftSize-1],右子树范围为[postL+leftSize,postR]
    root->right = createTree(preL+leftSize+1,preR,postL+leftSize,postR-1);
    return root;
}
int num = 0;
void inOrder(Node* root){
    if(root==nullptr) return;
    inOrder(root->left);
    printf("%d",root->v);
    if(num<n-1){
        printf(" ");
    }else{
        printf("\n");// 最后得换行
    }
    ++num;
    inOrder(root->right);
}

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&pre[i]);
    }
    for(int i=0;i<n;++i){
        scanf("%d",&post[i]);
    }
    Node* root = createTree(0,n-1,0,n-1);
    if(!multiChoice){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    inOrder(root);
    return 0;
}

PAT题解

关注专栏