題目：

給定一棵二叉樹的后序遍歷和中序遍歷，請(qǐng)你輸出其層序遍歷的序列。這里假設(shè)鍵值都是互不相等的正整數(shù)。

輸入格式：

輸入第一行給出一個(gè)正整數(shù)N（≤30），是二叉樹中結(jié)點(diǎn)的個(gè)數(shù)。第二行給出其后序遍歷序列。第三行給出其中序遍歷序列。數(shù)字間以空格分隔。

輸出格式：

在一行中輸出該樹的層序遍歷的序列。數(shù)字間以1個(gè)空格分隔，行首尾不得有多余空格。

輸入樣例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

輸出樣例：

4 1 6 3 5 7 2

ac代碼：

#include<iostream>
#include<queue>
#include<vector>
#define MAXSIZE 50
using namespace std;

int postorder[30], inorder[30], n;
vector<int> ans;
//bool visited[MAXSIZE] = { false };
typedef struct TNode* Node;
struct TNode {
    int num;
    Node left, right;
};
Node Build(int L1, int R1, int L2, int R2)
{
    if (L1 > R1)
        return NULL;
    Node root = new TNode;
    root->num = postorder[R2];//后序遍歷末位數(shù)
    int p = L1;
    while (inorder[p] != root->num)
        p++;
    int ln = p - L1;//左子樹節(jié)點(diǎn)數(shù)量
    root->left = Build(L1, p - 1, L2, L2 + ln - 1);     //L2,p-1);
    root->right = Build(p + 1, R1, L2 + ln, R2 - 1);    //p,R2-1);
    return root;
}

void BFS(Node root)
{
    queue<Node> Q;
    Q.push(root);
    while (!Q.empty())
    {
        Node u = Q.front();
        Q.pop();
        ans.push_back(u->num);
        if (u->left != NULL)
            Q.push(u->left);
        if (u->right != NULL)
            Q.push(u->right);
    }
}

int main()
{
    Node root = NULL;
    cin >> n;
    if (n == 0) {
        root = NULL;
        system("pause");
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> postorder[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
    }
    root = Build(0, n - 1, 0, n - 1);
    BFS(root);
    for (int i = 0; i < ans.size(); i++)
    {
        if (i != 0)
            cout << " ";
        cout << ans[i];
    }
    cout << endl;
    system("pause");
    return 0;
}

在ac之前自己硬是把隊(duì)列的做法又寫了一遍

#include<iostream>
#define MAXSIZE 50
using namespace std;

int postorder[30], inorder[30], n;
typedef struct TNode* Node;
struct TNode {
    int num;
    Node left, right;
};
typedef struct queue {
    Node data[MAXSIZE];
    int front;
    int rear;
};

void CreateQueue(queue* Q) 
{
    Q->front = Q->rear = 0;
}

int EmptyQuene(queue* Q)
{
    if (Q->front == Q->rear)
        return 1;
    else return 0;
}

void EnQueue(queue *Q, Node n)
{
    if (Q->rear - Q->front == MAXSIZE - 1)
    {
        cout << "隊(duì)列已經(jīng)滿了" << endl;
        return;
    }
    else
    {
        Q->data[Q->rear] = n;
        Q->rear++;
    }
}

int DeQueue(queue* Q)
{
    if (EmptyQuene(Q) == 1)
        return -1;
    int n = Q->data[Q->front]->num;
    Q->front++;
    return n;
}

Node Front(queue *Q)
{
    return Q->data[Q->front];
}

Node Build(int L1, int R1, int L2, int R2)
{
    if (L1 > R1)
        return NULL;
    Node root = new TNode;
    root->num = postorder[R2];//后序遍歷末位數(shù)
    int p = L1;
    while (inorder[p] != root->num)
        p++;
    int ln = p - L1;//左子樹節(jié)點(diǎn)數(shù)量
    root->left = Build(L1, p - 1, L2, L2 + ln - 1);     //L2,p-1);
    root->right = Build(p + 1, R1, L2 + ln, R2 - 1);    //p,R2-1);
    return root;
}

void BFS(Node root)
{
    queue* Q = new queue;
    CreateQueue(Q);
    EnQueue(Q, root);
    while (!EmptyQuene(Q))
    {
        Node u = Front(Q);
        int k = DeQueue(Q);
        cout << k << " ";
        if (u->left != NULL)
            EnQueue(Q, u->left);
        if (u->right != NULL)
            EnQueue(Q, u->right); 
    }
}

int main()
{
    Node root = NULL;
    cin >> n;
    if (n == 0) {
        root = NULL;
        system("pause");
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> postorder[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
    }
    root = Build(0, n - 1, 0, n - 1);
    BFS(root);
    cout << endl;
    system("pause");
    return 0;
}