题目链接：https://www.patest.cn/contests/pat-a-practise/1020
题目大意：已知树的后序遍历和中序遍历，求该树的层次遍历
解题思路：
先根据后序和中序确定树的结构再进行层次遍历即可代码如下：
#include<iostream> #include<vector> #include<queue> using namespace std; struct Node{ int data; Node* lchild; Node* rchild; }; int post[32];//后序遍历序列 int in[32];//中序遍历序列 Node* create(int pL,int pR,int iL,int iR){//pL,pR为后序序列左右端点；iL,iR为中序序列左右端点 if(pL>pR)return NULL; Node* root=new Node;//建立根节点 root->data=post[pR]; int index; for(index=iL;index<=iR;index++){//在中序序列中找到根节点 if(in[index]==post[pR]) break; } int numleft=index-iL; root->lchild=create(pL,pL+numleft-1,iL,index-1);//递归地建立左子树 root->rchild=create(pL+numleft,pR-1,index+1,iR);//递归地建立右子树 return root; } int firstflag=0;//标记是否输出的为第一个节点 void levelOrder(Node *p){ queue<Node*> que; que.push(p); while(!que.empty()){ Node* tmp=que.front(); que.pop(); if(firstflag!=0)//若不是第一个节点，先输出空格 cout<<" "; cout<<tmp->data;//再输出值 firstflag=1; if(tmp->lchild!=NULL) que.push(tmp->lchild); if(tmp->rchild!=NULL) que.push(tmp->rchild); } } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>post[i]; } for(int i=0;i<n;i++){ cin>>in[i]; } Node* root=create(0,n-1,0,n-1); levelOrder(root); return 0; }