给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
分析:
使用递归建树,每次找出区间中的根节点,用l[N]来存左子树,用r[N]来存右子树,从根节点一分为二,继续递归遍历,实现二叉树的建立,然后可以用宽度优先搜索依次输出节点,用队列存下根节点开始BFS(),实现输出。
代码:
#include <iostream> #include <cstdio> #include <queue> using namespace std; const int N=40; int l[N],r[N],a[N],b[N],p[N]; int n; int build(int al,int ar,int bl,int br) { if(al>ar) return 0; int val=a[ar]; int k=p[val]; l[val]=build(al,al+k-bl-1,bl,k-1); r[val]=build(al+k-bl,ar-1,k+1,br); return val; } void bfs() { queue<int> q; q.push(a[n-1]); while(q.size()) { int t=q.front(); q.pop(); if(l[t]) q.push(l[t]); if(r[t]) q.push(r[t]); printf("%d",t); if(q.empty()) printf("\n"); else printf(" "); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&b[i]); for(int i=0;i<n;i++) p[b[i]]=i; build(0,n-1,0,n-1); bfs(); return 0; }
标签:遍历,val,int,al,bl,二叉树 From: https://www.cnblogs.com/yaowww/p/17320216.html