#include<bits/stdc++.h>
using namespace std;
int main(){
struct Node {
int val,l,r;
} node[MAX];
int tot;
int c[MAX],b[MAX];
int dfs(int len,int b[],int c[]) {//中序，后序
if(len <= 0) return -1;
if(len == 1) {
node[++tot].val = b[1];
node[tot].l=node[tot].r = -1;
return tot;
}
node[++tot].val = c[len];
int res = tot;
int l;
for(l = 1; l<=len; l++) { //找到切割点
if(b[l] == c[len]) break;
}
node[res].l = dfs(l-1,b,c);//进去后 node[res].r = dfs(len-l,b+l-1,c+l);
node[res].r = dfs(len-l,b+l,c+l-1);
return res;
}
void bfs() { //层序遍历
queue<int> q;
q.push(1);
while(q.size()) {
int cur = q.front();
q.pop();
if(cur != 1) printf(" ");
printf("%d",node[cur].val);
if(node[cur].l != -1) q.push(node[cur].l);
if(node[cur].r != -1) q.push(node[cur].r);
}
}
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) scanf("%d",c+i);
for(int i = 1; i<=n; i++) scanf("%d",b+i);
dfs(n,b,c);
bfs(); //在这里有打印操作
return 0 ;
}
【7-10 PAT】树的遍历（给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。）
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目 1020 Tree Traversals （25 分）Suppose that all the keys i...
- 二叉树附demo，前序遍历、后序遍历、层序遍历、删除一个二叉树的节点，前驱后继节点等概念啊和原理 demo 基本概...
