前几天去刷了PAT，趁热把答案记录下来供大家参考
这题完全是英语阅读题，题目读懂就能写
题意：BST，给中序序列和后序序列，重建这颗树，并将树按"Z"字型输出
#include<stdio.h> #include<queue> #include<vector> using namespace std; int n; int in[40], post[40]; struct node{ int data; int level; node* left; node* right; node():left(NULL),right(NULL){} }; node* creat(int inL, int inR, int postL, int postR){ if(inL>inR)return NULL; node* root=new node; root->data=post[postR]; int k; for(k=inL;k<=inR;k++){ if(in[k]==post[postR])break; } int num_left=k-inL; root->left=creat(inL,k-1,postL,postL+num_left-1); root->right=creat(k+1,inR,postL+num_left,postR-1); return root; } int max_level=0; vector<int> ve[40]; void BFS(node* root){ queue<node*> q; root->level=1; q.push(root); while(!q.empty()){ node* front=q.front(); q.pop(); ve[front->level].push_back(front->data); if(front->level>max_level)max_level=front->level; if(front->left!=NULL){ front->left->level=front->level+1; q.push(front->left); } if(front->right!=NULL){ front->right->level=front->level+1; q.push(front->right); } } } int main(){ int i, j, total=0; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&in[i]); } for(i=0;i<n;i++){ scanf("%d",&post[i]); } node* root=creat(0,n-1,0,n-1); BFS(root); for(i=1;i<=max_level;i++){ if(i==1||i%2==0){ for(j=0;j<ve[i].size();j++){ printf("%d",ve[i][j]); total++; if(total<n)printf(" "); } } else{ for(j=ve[i].size()-1;j>=0;j--){ printf("%d",ve[i][j]); total++; if(total<n)printf(" "); } } } return 0; }