L2-006. 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式： 输入第一行给出一个正整数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

解析：根据后序遍历可确定根（后序遍历最后一位），知道根可以在中序遍历找到左子树中序遍历序列和右子树中序遍历序列（根的前边为左子树后边为右子树）

#include<iostream> #include<cstdio> #include<queue> using namespace std; int be[100],mi[100]; struct node { int l,r; }father[100]; int find(int mil,int mir,int bel,int ber) { int root,p1,p2; if(mil>mir) return 0; root=be[ber]; p1=mil; //p1根的位置 while(mi[p1]!=root) p1++; p2=p1-mil; //p2左子树的长度,根据p1来确定前序遍历的起点和终点,根据p2来确定后序遍历的起点和终点 father[root].l=find(mil,p1-1,bel,bel+p2-1); father[root].r=find(p1+1,mir,bel+p2,ber-1); return root; } void bfs(int v) { int i=0,a[100]; queue<int>s; s.push(v); while(!s.empty()) { int w=s.front(); s.pop(); a[i++]=w;//保存层序遍历 if(father[w].l!=0) s.push(father[w].l); if(father[w].r!=0) s.push(father[w].r); } for(int j=0;j<i;j++) printf("%d%c",a[j],j==i-1?'\n':' '); } int main() { int n,i; cin>>n; for(i=0;i<n;i++) cin>>be[i]; for(i=0;i<n;i++) cin>>mi[i]; find(0,n-1,0,n-1); bfs(be[n-1]); }