做任务免费领取东西的网站,设计公司装修图,wordpress 分享主题,商业网站建设公司L2-006. 树的遍历 时间限制400 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者陈越给定一棵二叉树的后序遍历和中序遍历#xff0c;请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式#xff1a; 输入第一行给出一个正整数N#xff08;请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式 输入第一行给出一个正整数N30是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。 输出格式 在一行中输出该树的层序遍历的序列。数字间以1个空格分隔行首尾不得有多余空格。 输入样例 7
2 3 1 5 7 6 4
1 2 3 4 5 6 7输出样例 4 1 6 3 5 7 2分析 这道题和pat l2-004简直就是同一道题目啊... 只不过那题是给你中序和先序...一个意思嘛 在先序或后序中只要我们知道了左子树或者右子树的范围我们就可以找到根节点的值从而在中序中找到根节点的位置然后递归去做同样的步骤就好啦。层序遍历其实就是bfs啦用用队列就好了... 1 #includebits/stdc.h2 using namespace std;3 const int maxn1e5;4 int mid[32], bk[32], tree[maxn];5 struct node{6 int l, r;7 }a[maxn];8 int build(int la, int lb, int ra, int rb){9 if(lalb) return 0;
10 int rootbk[rb];
11 int p1, p2;
12 p1la;
13 while(root!mid[p1]) p1;
14 p2p1-la;
15 a[root].lbuild(la, p1-1, ra, rap2-1);
16 a[root].rbuild(p11, lb, rap2, rb-1);
17 return root;
18 }
19 void bfs(int x){
20 int cnt0;
21 queueintq;
22 q.push(x);
23 while(q.size()){
24 int mq.front(); q.pop();
25 cnt1? coutm:cout m;
26 if(a[m].l!0)
27 q.push(a[m].l);
28 if(a[m].r!0)
29 q.push(a[m].r);
30 }
31 }
32 int main(){
33 int n;
34 cinn;
35 for(int i0; in; i)
36 cinbk[i];
37 for(int i0; in; i)
38 cinmid[i];
39 int rootbuild(0, n-1, 0, n-1);
40 bfs(root);
41
42 return 0;
43 } 转载于:https://www.cnblogs.com/ledoc/p/6591900.html
