题目信息：https://www.patest.cn/contests/pat-a-practise/1020
提交情况：
代码：
#include <iostream> #include <malloc.h> #include <vector> using namespace std; #define N 33 typedef struct BTree { int data; struct BTree* leftTree; struct BTree* rightTree; }BTree; //n为节点个数，post[]代表后序遍历序列，in[]代表中序遍历序列 //front和rear为树队列的下标 int n,post[N],in[N],front,rear; BTree* queue[N]; //用于存储二叉树的层次遍历的节点信息。因为题目要求最后不能有空，不好控制（或者说我不会，欢迎大神指点） vector<int> num; //根据后序和中序序列构造二叉树 BTree* creat( int post[],int in[],int length ) { if( length == 0 ) return NULL; else { BTree *root = (BTree*)malloc(sizeof(BTree)); root->data = post[length]; int i = 1; while( post[length] != in[i] && i<=length ) ++i; //通过控制post和in的起始地址和长度来控制左右子树的范围 //post[0]代表偏移量为0,即post不做偏移，等价于*(post+0) //post[1]代表偏移量为1,即post偏移sizeof(int)个字节数，等价于*(post+1) //其实下面的两句代码才是关键， 控制post和in的起始地址 root->leftTree = creat(post,in,i-1); root->rightTree = creat(post+i-1,in+i,length-i); return root; } } //树层次遍历和图的广度遍历相似，而树是一种特殊的图，只有n-1条边，其中n为节点个数 void BFS( BTree *root ) { queue[++rear] = root; while( front != rear ) { BTree* bt = queue[++front]; num.push_back(bt->data); if( bt->leftTree != NULL ) { queue[++rear] = bt->leftTree; } if( bt->rightTree != NULL ) { queue[++rear] = bt->rightTree; } } } //前序遍历 void preOrder( BTree *bt ) { if( bt != NULL ) { cout<<bt->data<<" "; preOrder(bt->leftTree); preOrder(bt->rightTree); } } int main() { cin>>n; for( int i=1;i<=n;++i ) //数组下标从1开始 cin>>post[i]; //输入后序遍历的序列 for( int i=1;i<=n;++i ) //数组下标从1开始 cin>>in[i]; //输入中序遍历的序列 BTree *root = creat(post,in,n); // preOrder(root); // cout<<"前序遍历结束"<<endl; //层次遍历前的初始化,初始化队列queue的下标 front = rear = -1; BFS(root); for( int i=0;i<num.size();++i ) { if( i == num.size()-1 ) cout<<num[i]<<endl; else cout<<num[i]<<" "; } return 0; }