关于c++:PAT甲级1119-Pre-and-Postorder-Traversals

题目粗心

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

算法思路

在给定先序和后序序列后，咱们只能通过先序第一个节点和后序最初一个节点相等来判断残余的左右子树的范畴，然而对于先序和后序中的左右子树的绝对程序是统一的，那么咱们能够设置左子树的长度为 leftSize，从 0 开始进行遍历，只有先序的左子树节点汇合和后序的左子树节点汇合雷同 (程序能够不一样)，同时先序左子树的首节点和后序左子树的尾节点是雷同的，这样咱们就失去了一个胜利的左右子树的划分，又因为咱们须要判断是否有多种划分后果，在第一次获得成功划分的时候须要持续进行查找，直到取得第二次胜利划分或者没有第二次划分从而退出循环。这里对建树的操作作进一步细说，

• 1、咱们应用 count 记录以后子树划分胜利的次数，初始为 0
• 2、初始设置左子树长度为 0，判断是否能够胜利划分的根据就是先序的左子树首节点和后序左子树尾结点是否相等
• 3、判断先序和后序左子树汇合是否雷同的办法，就是应用一个 set 汇合一次填入先序左子树和后序左子树的节点，其长度恰好为左子树长度就阐明先序和后序左子树汇合雷同
• 4、在每一次获取胜利的划分后就应用 leftSize 进行记录，并应用全局变量 multiChoice 记录是否有多个划分可能。
• 5、划分结束之后，先序的左子树范畴为 [preL+1,preL+leftSize]，右子树范畴为 [preL+leftSize+1,preR]。后序的左子树范畴为 [postL,postL+leftSize-1], 右子树范畴为 [postL+leftSize,postR]

提交后果

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;
}