postorder后序遍历（需要完整代码）

Question

题目描述

Given the pre-order traversal sequence A[] and in-order traversal sequence B[] of a tree, find the post-order traversal sequence.
输入描述

Input contains 3 lines;
The first line contains an integer n(n <= 100000), the number of node in the tree.
The second line contains n distinct intergers, which is the sequence A[](0 <= a0,a2,…,an-1<= n-1).
The third line contains n distinct intergers, which is the sequence B[](0 <= b0,b2,…,bn-1<= n-1).
输出描述

The postorder traversal sequence of the tree.
输入样例

10
7 2 0 5 8 4 9 6 3 1
7 5 8 0 4 2 6 3 9 1
输出样例

8 5 4 0 3 6 1 9 2 7

Answer 1

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int pos, n;

vector<int> pre, in, post;

void rec(int l, int r)
{
    if (l >= r)
        return;
    int root = pre[pos++];
    int mid = distance(in.begin(), find(in.begin(), in.end(), root));
    rec(l, mid);
    rec(mid + 1, r);
    post.push_back(root);
}

void solve()
{
    pos = 0;
    rec(0, pre.size());
    for (int i = 0; i < post.size(); i++)
    {
        if (i)
            cout << " ";
        cout << post[i];
    }
    cout << endl;
}

int main()
{
    while (cin >> n)
    {
        pre.clear();
        in.clear();
        post.clear();

        for (int i = 0; i < n; i++)
        {
            int k;
            cin >> k;
            pre.push_back(k);
        }

        for (int i = 0; i < n; i++)
        {
            int k;
            cin >> k;
            in.push_back(k);
        }

        solve();
    }
    return 0;
}