PAT [1127] ZigZagging on a Tree (30)

发表于 | 分类于

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” — that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input 

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

Sample Output 

1
1 11 5 8 17 12 20 15

Algorithm：
树：根据树的中序与后序遍历构建树并以z字形层次输出

Learn：
0、可以不用构建树就可以输出，学会考虑在构建的过程中多做点文章

code

首先是构建树后再z字形层次打印树，多次一举代码也比较冗余：

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

struct node
{
	int data;
	node *l;
	node *r;
	int deep;
	node(int x=0):data(x){
		l=NULL;
		r=NULL;
	}
};

int in[8]={12,11,20,17,1,15,8,5};//中序遍历 
int post[8]={12,20,17,11,15,8,5,1};//后序遍历 

vector<vector<int> > level(35);

node* buildTree(int inl,int inr,int postl,int postr,int deep)//递归，子情况！ 
{
	if(postl>postr)  return NULL; 
	
	int k;
	for(k=inl;in[k]!=post[postr]&&k<=inr;k++);//找到这个根节点在中序遍历中的位置
	
	node* newNode=new node(post[postr]);//创建新节点
	newNode->deep=deep;
	level[deep].push_back(post[postr]);
	int num=k-inl-1;
	newNode->l=buildTree(inl,k-1,postl,postl+num,deep+1);//左子树 
	newNode->r=buildTree(k+1,inr,postl+num+1,postr-1,deep+1);//右子树 
	
	return newNode; 
}

void zigzagging(node* root)//偶数层入栈  数层直接输出 
{
	queue<node*> q;
	int nowDeep=0; 
	bool dirct=1;
	q.push(root);
	vector<int> v;
	vector<int>::iterator it;
	vector<int>::reverse_iterator rit;
	
	while(!q.empty())
	{ 	
		node* temp=q.front();
		q.pop(); 
		
		if(nowDeep!=temp->deep){//如果换行了  
			
			nowDeep=temp->deep; 
			
			dirct=!dirct;
			
			if(dirct==0)//正向 
			{	 
				for(it=v.begin();it!=v.end();it++)
					cout<<*it<<" ";
				v.clear();
			} 
			else//反向输出 
			{
				for(rit=v.rbegin();rit!=v.rend();rit++)
					cout<<*rit<<" ";
				v.clear();
			}
			cout<<endl;
		} 
		
		v.push_back(temp->data);
		
		if(temp->l)
			q.push(temp->l);
		if(temp->r)
			q.push(temp->r);
	}
	
	if(dirct==1)//正向 
	{	 
		for(it=v.begin();it!=v.end();it++)
			cout<<*it<<" ";
		v.clear();
	} 
	else//反向输出 
	{
		for(rit=v.rbegin();rit!=v.rend();rit++)
			cout<<*rit<<" ";
		v.clear();
	}
}

int main()
{
	node*root =buildTree(0,7,0,7,0);//构建这颗树
	zigzagging(root);
	return 0;
}

因为在根据后序和中序构建的过程中的递归刚好是顺序的，所以可以在构建的时候直接根据深度把他保存在一个数组中就好。

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
using namespace std;

struct node
{
	int data;
	node *l;
	node *r;
	int deep;
	node(int x=0):data(x){
		l=NULL;
		r=NULL;
	}
};

int in[8]={12,11,20,17,1,15,8,5};//中序遍历 
int post[8]={12,20,17,11,15,8,5,1};//后序遍历 

vector<vector<int> > level(35);

void buildTree(int inl,int inr,int postl,int postr,int deep)//递归，子情况！ 
{
	if(postl>postr)  return; 
	int k;
	for(k=inl;in[k]!=post[postr]&&k<=inr;k++);//找到这个根节点在中序遍历中的位置
	level[deep].push_back(post[postr]);
	int num=k-inl-1;
	buildTree(inl,k-1,postl,postl+num,deep+1);//左子树 
	buildTree(k+1,inr,postl+num+1,postr-1,deep+1);//右子树 
	
}

int main()
{
	buildTree(0,7,0,7,0);//构建这颗树
	
	for(int i=0;i<level.size()&&level[i].size()!=0;i++)
	{
		if(i%2==0)
		{
			for(int j=0;j<level[i].size();j++)
			{
				cout<<level[i][j]<<" ";
			} 
			cout<<endl;
		} 
		else
		{
			for(int j=level[i].size()-1;j>=0;j--)
			{
			    cout<<level[i][j]<<" ";
			}
			cout<<endl; 
		}
	} 

	return 0;
}