Skip to content

L2-011 玩转二叉树

Statement

Metadata

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

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式

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

输出格式

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

输入样例 

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

输出样例 

4 6 1 7 5 3 2

Solution

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

#define ll long long
#define db double
#define N 100010
int n, a[50], b[50];
struct node {
    int ls, rs;
    node() {}
    node(int ls, int rs) : ls(ls), rs(rs) {}
} arr[N];
vector<int> res;

int DFS(int al, int ar, int bl, int br) {
    if (al > ar)
        return -1;
    if (al == ar)
        return b[bl];
    int root = b[bl];
    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 + 1, bl + sze);
    arr[root].rs = DFS(pos + 1, ar, bl + sze + 1, br);
    return root;
}

void rev(int u) {
    if (u == -1)
        return;
    swap(arr[u].ls, arr[u].rs);
    rev(arr[u].ls);
    rev(arr[u].rs);
}

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

int main() {
    while (scanf("%d", &n) != EOF) {
        memset(arr, -1, sizeof arr);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = 1; i <= n; ++i) scanf("%d", b + i);
        res.clear();
        int root = DFS(1, n, 1, n);
        rev(root);
        BFS(root);
        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