【1127】ZigZagging on a Tree (30分)【中后序建树 层次】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<string>
using namespace std;
vector<int>postorder(31);
vector<int>inorder(31);
vector<vector<int>>levels(31);

void buildTree(int postl,int postr,int inl,int inr,int level){
if(postl>postr || inl>inr) return;
int root=postorder[postr];//root为根结点，在后序遍历最后一个位置上
int i=0;
while(inorder[inl+i] !=root)//在中序遍历序列中查找根结点位置
i++;//跳出while时得到i，左子树结点个数为i
levels[level].push_back(root);//把根结点存入对应层的vector中
buildTree(postl, postl+i-1, inl, inl+i-1, level+1);//建立左子树
buildTree(postl+i, postr-1, inl+i+1, inr, level+1);//建立右子树
//后序遍历： 左子树(postl ...postl+i-1) 右子树(post+i ... postr-1) root=postr-1
//中序遍历 ： 左子树(inl...inl+i-1) root=inl+i 右子树(inl+i+1...inr)
}
void zigzag(){//Z型的层序遍历
cout<<levels[0][0];
bool zigzag=false;
for(int i=1;i<levels.size()&& !levels[i].empty();i++){
//注意levels.size()为树的层数 并且判断了当前层的结点数不为空的时候
if(zigzag){
for(int j=levels[i].size()-1;j>=0;j--){
cout<<" "<<levels[i][j];
}
}
else{
for(int j=0;j<levels[i].size();j++){
cout<<" "<<levels[i][j];
}
}
zigzag=!zigzag;
}
}
int main(){
int N;
while(cin>>N){
for(int i=0;i<N;i++){
cin>>inorder[i];//存入中序遍历序列
}
for(int i=0;i<N;i++){
cin>>postorder[i];//存入后序遍历序列
}
buildTree(0,N-1,0,N-1,0);
zigzag();
}
system("pause");
return 0;
}

和晴神差不多的版本

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
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* create(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]){//在中序序列中找到in[k]==post[postR]的结点
break;
}
}
int num_Left=k-inL;//左子树的结点个数
//返回左子树的根结点地址，赋值给root的左指针
root->left=create(inL,k-1,postL,postL+num_Left-1);
root->right=create(k+1,inR,postL+num_Left,postR-1);
//返回右子树的根结点地址，赋值给root的右指针
return root;
}
int max_level=0;
vector<int> ve[40];
void BFS(node* root){
queue<node*>q;
root->level=1;//一开始漏了这句，导致跳出读取位置 xxx时发生访问冲突 的报错
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
ve[now->level].push_back(now->data);
if(now->level>max_level) max_level=now->level;
if(now->left!=NULL){
now->left->level=now->level+1;
q.push(now->left);
}
if(now->right!=NULL){
now->right->level=now->level+1;
q.push(now->right);
}
}
}

int main(){
int i,j,total=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
}
node* root=create(0,n-1,0,n-1);
BFS(root);
for(int i=1;i<=max_level;i++){
if(i==1||i%2==0){
for(int j=0;j<ve[i].size();j++){
printf("%d",ve[i][j]);
total++;
if(total<n) printf(" ");
}
}else{
for(int j=ve[i].size()-1;j>=0;j--){
printf("%d",ve[i][j]);
total++;
if(total<n) printf(" ");
}
}
}
system("pause");
return 0;
}