1138. Postorder Traversal.md

【PAT A-1138】Postorder Traversal

题意概述

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

输入输出格式

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

输出该树的后根遍历序列的第一个数。

数据规模

$$0<N\le 50000$$

算法设计

由于只要求输出要求输出该树的后根遍历序列的第一个数，没有必要重建这棵树，也没有必要获取整个后根序列。我们需要在原有算法上进行一些改动，让它能找到后根序列的第一个数即可。

那么如何找到这个数呢？我们知道后根遍历是按照“左右中”的顺序进行遍历的，所以对于以某个结点为根的树来说，如果它有左子树，则我们要找的数必然在左子树中；如果根结点没有左子树，有右子树，则我们要找的数必然在右子树中；如果根结点是个叶结点，则我们要找的数就是它本身。我们根据这样的顺序就可以很快的找到后根序列的第一个数了。具体实现可见代码。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
void getPostFromPreIn(vector<gg>& pre, vector<gg>& in, gg r, gg left, gg right) {
    if (left == right) {
        cout << pre[r];
        return;
    }
    gg i = find(in.begin(), in.end(), pre[r]) - in.begin();
    if (i > left) {  //左子树不空，向左子树中查找
        getPostFromPreIn(pre, in, r + 1, left, i - 1);
    } else {  //左子树为空，向右子树中查找
        getPostFromPreIn(pre, in, r + 1 + i - left, i + 1, right);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    vector<gg> pre(ni), in(ni);
    for (gg& i : pre) {
        cin >> i;
    }
    for (gg& i : in) {
        cin >> i;
    }
    getPostFromPreIn(pre, in, 0, 0, ni - 1);
    return 0;
}