第七周 L2-006 树的遍历

题目：

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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];//后序遍历末位数
    int p = L1;
    while (inorder[p] != root->num)
        p++;
    int ln = p - L1;//左子树节点数量
    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之前自己硬是把队列的做法又写了一遍

#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 << "队列已经满了" << 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];//后序遍历末位数
    int p = L1;
    while (inorder[p] != root->num)
        p++;
    int ln = p - L1;//左子树节点数量
    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;
}