1127

简介: #include #include #include using namespace std;int n;const int maxn = 31;struct node { int data; node *l,...
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
const int maxn = 31;
struct node { int data; node *l, *r;};
vector<int> post(maxn), in(maxn), ans, lnum(maxn);

node* build(int postL, int postR, int inL, int inR){//根据后序和中序建树
    if(postL > postR) return NULL;
    node *root = new node;
    root->data = post[postR];
    int k;
    for (k = inL; k <= inR; k++)
        if(in[k] == post[postR]) break;
    int numLeft = k - inL;
    root->l = build(postL, postL + numLeft - 1, inL, k - 1);
    root->r = build(postL + numLeft, postR - 1, k + 1, inR);
    return root;
}
void dfs(node *root, int depth){//求每一层的个数
    if (root == NULL) return;
    lnum[depth]++;
    if(root->l != NULL) dfs(root->l, depth + 1);
    if(root->r != NULL) dfs(root->r, depth + 1);
}
void bfs(node *root){//层序遍历的结果存在ans中
    queue<node*> q;
    q.push(root);
    while (!q.empty()) {
        node *now = q.front();
        q.pop();
        ans.push_back(now->data);
        if(now->l) q.push(now->l);
        if(now->r) q.push(now->r);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> in[i];
    for(int i = 0; i < n; i++) cin >> post[i];
    node *root = build(0, n - 1, 0, n - 1);
    dfs(root, 0);
    bfs(root);
    //z输出
    int cnt = 0;
    printf("%d", ans[cnt++]);
    for (int i = 1; i < maxn;) {
        if (i % 2) {
            for (int j = 0; j < lnum[i]; j++)
                printf(" %d", ans[cnt+j]);
            cnt = cnt + lnum[i];
            i++;
        }else{
            for (int j = lnum[i] - 1; j >= 0; j--)
                printf(" %d", ans[cnt+j]);
            cnt = cnt + lnum[i];
            i++;
        }
    }
    cout << endl;

    return 0;
}
目录
相关文章
|
7月前
|
监控 物联网 应用服务中间件
流媒体方案之Nginx——实现物联网视频监控项目
流媒体方案之Nginx——实现物联网视频监控项目
流媒体方案之Nginx——实现物联网视频监控项目
|
4月前
|
JSON 自然语言处理 数据库
Elasticsearch从入门到项目部署 安装 分词器 索引库操作
这篇文章详细介绍了Elasticsearch的基本概念、倒排索引原理、安装部署、IK分词器的使用,以及如何在Elasticsearch中进行索引库的CRUD操作,旨在帮助读者从入门到项目部署全面掌握Elasticsearch的使用。
|
5月前
|
JavaScript
js 判断字符串是否包含中文,判断字符串是否全是中文,判断字符是否为中文
js 判断字符串是否包含中文,判断字符串是否全是中文,判断字符是否为中文
261 0
|
4月前
|
人工智能 搜索推荐 API
AI智能体研发之路-工程篇(二):Dify智能体开发平台一键部署
AI智能体研发之路-工程篇(二):Dify智能体开发平台一键部署
673 3
|
7月前
|
缓存 前端开发 JavaScript
解决白屏问题:让你的网站重焕生机
解决白屏问题:让你的网站重焕生机
|
7月前
|
安全 网络协议 Linux
|
存储 SQL 关系型数据库
【Mysql-InnoDB 系列】事务提交过程
MySQL InnoDB的事务模型、锁机制等设计,都是InnoDB架构设计的一部分。要全面了解它的设计实践,就必须从头看起。只有这样,才能够弄清楚它的设计思想,理解其实现上的精妙之处。
584 1
|
机器学习/深度学习 并行计算 算法
机器学习算法对GPU的要求分析
简单介绍做机器学习算法的厂家对GPU的要求
536 1
|
程序员
代码的规范
代码的规范
164 0
|
人工智能 搜索推荐 物联网
web1.0 和 web2.0 以及 web3.0的发展史
web1.0 和 web2.0 以及 web3.0的发展史
1169 0