1119 Pre- and Post-order Traversals (30 分)

pat的格式很严格，最后要输出空行，然后是思路，如果一棵二叉树里面有结点只有一个孩子，那么就不能用先序后序来确定他，因为先序是先左后右，后序是先右后左，有两个结点，并且结点的值互不相等，先序和后序是不一样的，如果只有一个孩子，先序是遍历他，后序也是遍历他，这样孩子是左结点还是右结点，他的先序遍历和后序遍历相同，在这个孩子下面子孙结构一样的前提下，所以此时可能有两种二叉树的结构，所以我们就看先序结点后面的和后序根节点前面的是不是一样，来判断，然后这个和能确定二叉树的结构的不同，当有一个结点的时候如果用下标判断，这个时候超出当前序列的范围了，甚至可能数组越界，所以我还是用map的写法，特判了相等

#include 

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pa;

const int N = 35;

struct node {
    int value;
    node *lchild, *rchild;
};

int pre[N], post[N], ok = 1;
vi v;
map mp;

node *create(int prel, int prer, int postl, int postr) {
    if (prel > prer) return NULL;
    if (prel == prer) {
        node* root = new node;
        root->value = pre[prel];
        root->lchild = root->rchild = NULL;
        return root;
    }
    node *root = new node;
    root->value = pre[prel];
    if (pre[prel + 1] == post[postr - 1]) ok = 0;
    int k = mp[pre[prel + 1]];
    int numleft = k - postl + 1;
    root->lchild = create(prel + 1, prel + numleft, postl, k);
    root->rchild = create(prel + numleft + 1, prer, k + 1, postr - 1);
    return root;
}

void inorder(node *root) {
    if (root == NULL) return;
    inorder(root->lchild);
    v.pb(root->value);
    inorder(root->rchild);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) { cin >> post[i]; mp[post[i]] = i; }
    node *root = create(0, n - 1, 0, n - 1);
    inorder(root);
    cout << (ok ? "Yes" : "No") << endl;
    for (int i = 0; i < sz(v); i++) cout << v[i] << (i < sz(v) - 1 ? " " : "");
    return 0;
}