题目大意就是根据树的后序遍历和中序遍历推出层序遍历。
很久没做过这种题了，正好借此复习一下数据结构。
首先是遍历的几个简单介绍。
前序遍历(preorder)：根结点->左子树->右子树。
中序遍历(inorder)：左子树->根结点->右子树。
后序遍历(postorder)：左子树->右子树->根结点。
层序遍历(level order)：从根开始,依次向下,每一层从左向右遍历。
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8
接着来讲讲后序+中序->层序or前序
我们可以根据后序遍历的最后一个点找到根节点，然后在中序遍历中找到这个根节点，在根节点左边的就是左子树，右边为右子树。进而可以在后序遍历中划出左子树和右子树。同理得到的左子树和右子树也按该方法处理，最后即可得到这棵树。
最后是代码实现。
二叉树用结构体指针处理。
上述思路用递归函数实现。每次递归更新子树的中后序遍历序列的起点和终点，返回当前树的根节点。当后序序列的长度小于零时递归结束。
层序遍历的输出用BFS输出即可。
#include <iostream> #include <string.h> #include <cstdio> #include <string> #include <queue> using namespace std; #define maxn 35 struct node { int data; node *l; node *r; }tr[maxn]; int n; int a[maxn],b[maxn]; node* fun(int s1,int t1,int s2,int t2) { if(s1>t1) return NULL; int pos; node *root=new node; root->data=a[t1]; for(int i=s2;i<=t2;i++) { if(b[i]==a[t1]) { pos=i; break; } } int ln=pos-s2; root->l=fun(s1,s1+ln-1,s2,pos-1); root->r=fun(ln+s1,t1-1,pos+1,t2); return root; } void BFS(node *root) { int cnt=0; node *t; queue<node*> q; q.push(root); while(!q.empty()) { t=q.front(); q.pop(); printf("%d",t->data); cnt++; if(cnt<n) printf(" "); if(t->l!=NULL) q.push(t->l); if(t->r!=NULL) q.push(t->r); } printf("\n"); } 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]); node *root=fun(0,n-1,0,n-1); BFS(root); return 0; }
原文：https://www.cnblogs.com/FTA-Macro/p/10453083.html
