Skip to content

L2-006 树的遍历

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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

输入格式

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

输出格式

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

输入样例 

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

输出样例 

4 1 6 3 5 7 2

Solution

#include <bits/stdc++.h>
using namespace std;

#define N 110000
struct node {
    int ls, rs;
    node() {}
    node(int ls, int rs) : ls(ls), rs(rs) {}
    void init() {
        ls = rs = -1;
    }
} arr[N];
int n, a[N], b[N];
vector<int> res;

int DFS(int al, int ar, int bl, int br) {
    if (al > ar)
        return -1;
    if (al == ar)
        return b[br];
    int root = b[br];
    int pos = -1;
    for (int i = al; i <= ar; ++i)
        if (a[i] == root) {
            pos = i;
            break;
        }
    int sze = pos - al;
    arr[root].ls = DFS(al, pos - 1, bl, bl + sze - 1);
    arr[root].rs = DFS(pos + 1, ar, bl + sze, br - 1);
    return root;
}

void BFS(int rt, vector<int> &res) {
    queue<int> q;
    q.push(rt);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        if (arr[u].ls != -1)
            q.push(arr[u].ls);
        if (arr[u].rs != -1)
            q.push(arr[u].rs);
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i < N; ++i) arr[i].init();
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = 1; i <= n; ++i) scanf("%d", b + i);
        for (int i = 1; i <= n; ++i) swap(a[i], b[i]);
        int rt = DFS(1, n, 1, n);
        BFS(rt, res);
        for (int i = 0; i < n; ++i) printf("%d%c", res[i], " \n"[i == n - 1]);
    }
    return 0;
}
Last update: May 4, 2022
Back to top