PAT甲级1020题（中序后序遍历得层次遍历）

二叉树题

PAT

发布日期: 2021-02-04

文章字数: 272

阅读时长: 1 分

阅读次数:

1.题目介绍

1020

postorder：后序遍历

inorder：中序遍历

preorder：先序遍历

level order：层次遍历

2.考察点，难度

二叉树类，Map容器插入方法，Vector容器的运用，二叉树遍历，难度中

3.解题代码

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
vector<int> post, in;   // 后序遍历和中序遍历
map<int, int> level;

void pre(int root, int start, int end, int index) {    // root是相对于后序遍历的
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;  // i是为了找到中序遍历时的根节点
    level[index] = post[root];
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);   // 左子树根开始递归
    pre(root - 1, i + 1, end, 2 * index + 2);               // 右子树根开始递归
}

int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &post[i]);
    for(int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n-1, 0, n-1, 0);
    auto it = level.begin();
    printf("%d", it->second);
    while(++it != level.end()) printf(" %d", it->second);
    return 0;
}