1127 ZigZagging on a Tree C++版

1127 ZigZagging on a Tree C++版

1.题意

给出一个中序遍历和后序遍历，然后让你求出该树的层次遍历的“之”字型输出。难点在于“之”字型输出。但是真有那么难么？o(￣▽￣)ｄ

2.分析

主要步骤如下：

• step 1:由给出的中序序列和后序序列，构建一棵二叉树，这里我不再啰嗦，如有不会的同学，请看我的博客 由中序和后序序列构建二叉树
• step 2:将得到的二叉树遍历一遍，写上树高
• step 3:使用先序遍历将节点遍历并输出到一个vector中，需要注意的是，并不是直接输出，而是将每层的节点放到指定的vector[i]中。并不需要真使用层序遍历，那样会麻烦很多
• step 4.“之”字型我们可以看成是偶数层时是反输出，奇数层是正输出。将输出的结果放到res结果中，然后控制res的输出空格即可。
  完整的实现代码如下：

3.代码

#include<cstdio>
#include<vector>
#include<iostream>
#define maxn 100
using namespace std;
struct node{
	int data;//值 
	int height;//高度 
	node* left;//左子树 
	node* right; //右子树 
}; 

int in[maxn];
int post[maxn];
vector<int> hei[maxn];
int N;

node* create(int postL,int postR,int inL,int inR){
	if(postL > postR){//说明到头了 
		return NULL; 
	}
	//下面这个就是建树的步骤 
	node* root = new node;
	root->data = post[postR];//新节点的数据域为根节点的值 
	int i;
	for(i = inL; i <= inR;i++ ){
		if(in[i] == post[postR]){//说明找到了相同值 
			break;
		}
	}
	int numLeft ;//表示的是这个根节点左侧的节点数
	numLeft = i - inL;
	root->left = create(postL,postL+numLeft-1,inL,i-1); //建左子树 
	root->right = create(postL+numLeft,postR-1,i+1,inR);//建右子树 
	return root; 
} 


//为二叉树设置树高 
void setHeight(node* &root,int height){
	root->height = height;
	if(root->left!=NULL) setHeight(root->left,height+1);//输出左子树 
	if(root->right!=NULL) setHeight(root->right,height+1);//输出右子树 
}

//层次遍历 
void levelTrav(node* root){
	hei[root->height].push_back(root->data);//写入树高 
	if(root->left!=NULL) levelTrav(root->left);
	if(root->right!=NULL) levelTrav(root->right);
}

int main(){
	cin >> N;
	int i;
	for(i = 0;i< N;i++){
		cin >> in[i];
	}
	for(i = 0;i< N;i++){
		cin >> post[i];
	}
	node* root = create(0,N-1,0,N-1);
	setHeight(root,0);//设置树高 		
	levelTrav(root);	
	i = 0;
	vector<int> res;//存放结果 
	while(hei[i].size() > 0){//如果还有数据的时候，继续输出 		
		if(i % 2 == 0){//如果是偶数 
			for(int j = hei[i].size() -1;j >= 0;j--){
				res.push_back(hei[i][j]); 								
			}
		}else{
			for(int j = 0;j<hei[i].size();j++){
				res.push_back(hei[i][j]); 							
			}
		}	
		i++;	
	}
	
	for(i = 0;i< res.size();i++){
		if(i!=res.size()-1) cout << res[i]<<" ";
		else cout <<res[i];
	}
}

4.测试用例

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

4
1 15 8 5
15 8 5 1

5.执行结果

一次AC