博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1127
阅读量:6295 次
发布时间:2019-06-22

本文共 1699 字,大约阅读时间需要 5 分钟。

#include 
#include
#include
using namespace std;int n;const int maxn = 31;struct node { int data; node *l, *r;};vector
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
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;}

转载地址:http://cmvta.baihongyu.com/

你可能感兴趣的文章
牛客网刷题汇总(一)附解析
查看>>
(转) Deep Learning in a Nutshell: Reinforcement Learning
查看>>
微信说中国人的国庆长假 境内游西湖外滩上榜
查看>>
VR/AR会是微信后马化腾进军的战场吗
查看>>
推荐系统的评分描述
查看>>
Junit测试中找不到junit.framework.testcase
查看>>
SAP HU02 to Unpack for HU, Need Transfer HU to Package Storage Type First.
查看>>
1.3. Getting Started Guides
查看>>
三十而立,立的是什么?(r11笔记第70天)
查看>>
Log4jdbc demo
查看>>
(13)[Xamarin.Android] 不同分辨率下的图片使用概论
查看>>
12.3、Libgdx的图像之截屏
查看>>
什么是PyTorch,为何要使用PyTorch
查看>>
对ESB概念的理解(转)
查看>>
Building for Production
查看>>
python 内部函数,以及lambda,filter,map等内置函数
查看>>
大家猜猜看除了围棋,人工智能下一个颠覆的领域是什么?
查看>>
SharePoint 2013 数据库中手动更新用户信息
查看>>
SharePoint 2013 表单认证使用ASP.Net配置工具添加用户
查看>>
《C程序员:从校园到职场》出版预告(1):从“高大上”到“柴米油盐”
查看>>