1119. Pre- and Post-order Traversals.md

【PAT A-1119】Pre- and Post-order Traversals

题意概述

给出一棵二叉树的先根遍历序列和后根遍历序列，要求输出该树的中根遍历序列。

输入输出格式

第一行给出一个正整数 N，表示二叉树中结点的总数。随后第二行给出先根遍历序列，第三行给出后根遍历序列。

在一行中打印二叉树的中根遍历序列。所有数字必须完全由一个空格分隔，并且行尾不得有多余的空格。

数据规模

$$0<N\le 30$$

算法设计

给出一棵二叉树的先根遍历序列和后根遍历序列，有时可以构建多种形态的二叉树。那么什么时候构成的树不唯一呢？当一个结点只有左子树或者只有右子树的时候树的形态就是不唯一的。那么根据这个性质就可以判断树的形态唯不唯一了。

由于本节已经花了很大篇幅讨论根据遍历序列重建二叉树的问题，笔者在这里就不赘述算法的具体逻辑了，你应该尝试着自行实现这样的算法。下面直接给出本题的实现代码，算法的细节方面留给你自己思考。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
vector<gg> pre(35), post(35), in;
bool yes = true;
void getInFromPrePost(gg root, gg left, gg right) {
    if (left > right)
        return;
    if (left == right) {
        in.push_back(pre[root]);
        return;
    }
    gg i = find(post.begin() + left, post.begin() + right, pre[root + 1]) -
           post.begin();
    if (i == right - 1) {
        yes = false;
    }
    getInFromPrePost(root + 1, left, i);
    in.push_back(pre[root]);
    getInFromPrePost(root + 2 + i - left, i + 1, right - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    for (gg i = 0; i < ni; ++i) {
        cin >> pre[i];
    }
    for (gg i = 0; i < ni; ++i) {
        cin >> post[i];
    }
    getInFromPrePost(0, 0, ni - 1);
    cout << (yes ? "Yes" : "No") << "\n";
    for (gg i = 0; i < ni; ++i) {
        cout << in[i] << (i == ni - 1 ? "\n" : " ");
    }
    return 0;
}