SJTU--1040 -- 二叉树层次遍历

本文主要是介绍SJTU--1040 -- 二叉树层次遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

1040. 二叉树层次遍历

Description

给出一棵二叉树，求它的层次遍历结果。

[二叉树的遍历问题是一种精神，务必领会]

Input Format

第一行，N<1000000，表示二叉树节点数。

默认序号为0的节点为树根。接下来共N-1行，依次表示序号为1，...，N-1的节点的父亲节点序号。

如果一个节点有两个孩子节点，左孩子节点序号总是小于右孩子节点序号。

Output Format

仅一行，二叉树的层次遍历结果。节点序号间用空格隔开。

Hint

Sample Input

6
0
1
1
0
4

Sample Output

0 1 4 2 3 5

 

 

 

Code:

 

第一次超时的

由于直接分配了一个超大的数组, 再根据数组中的数据逐个查找,  循环次数造成的时间复杂度那么大, 结果超时是必须的

 

#include"stdio.h"//超时代码,下面附的是正确AC的
#include"stdlib.h"
#include"queue"
#include"iostream"
using namespace std;
int tree[1000010];
int print[1000010];
int n;//n个结点 
queue <int> out; 
void Traverse(int tree[])
{
int i=0,j,num=0,pi=1,e;
out.push(i);//0入队	
for(j=1;j<=n;j++) 	
{		
num = 0;
e = out.front(); //出队一个元素并寻找以该元素为父节点的结点 		
out.pop();	
//	printf("e:%d \n",e);		
for(i=1;i<n;i++)//从0下标开始循环,父节点为i的入队并输出 		
{						
if(num==2) break;//两个子树 			
if(tree[i]==e)			
{			
//	printf("----\n");				
out.push(i);			
//	printf("back:%d \n",out.back());
print[pi++] = i;			
//	printf("print:%d \n",print[pi-1]);				
num++; 				
} 		
}	
}
} 
int main()
{ 	
int i;	
while(scanf("%d",&n)!=EOF)
{		
for(i=1;i<n;i++)			
scanf("%d",&tree[i]);//用数组存放父结点,下标代表结点元素 		
//	for(i=0;i<n;i++)		
//	print[i] = 0;					
print[0] = 0;		
Traverse(tree);				
for(i=0;i<n-1;i++)//输出 			
printf("%d ",print[i]);		
printf("%d\n",print[n-1]);		 	
}	
return 0;
}

第二次答案错误

手贱写错了数组下标, 楞了半天

 

第三次终于通过了,激动的泪流满面啊

 

#include"stdio.h"
#include"stdlib.h"
#include"queue"
#include"iostream"
using namespace std;
int tree[1000010][2];
int print[1000010]; 
int n;//n个结点
queue <int> out;
void Traverse(int tree[][2])
{
int e;
e = 0;
out.push(e);//先把0入队 
while(n--) //n次循环 
{
if(tree[e][0] != -1) out.push(tree[e][0]);//不为-1则入队 
if(tree[e][1] != -1) out.push(tree[e][1]);	
printf("%d",out.front());//输出队头元素 
if(n>0) printf(" "); 
out.pop();//出队已输出元素 
e = out.front();	 //e赋值为当前队头元素 
}
printf("\n");
}
int main()
{
int i,temp;	
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)//因为只可能有两颗子树, 所以如果输入的父亲结点相同的话,
tree[i][0] = tree[i][1] = -1; //放在这两个位置里面以节约时间 
for(i=1;i<n;i++)//用数组存放父结点,下标代表结点元素
{				
scanf("%d",&temp);
if(tree[temp][0] == -1)
{tree[temp][0] = i;}	
else//该父亲节点已经有一个孩子结点 
{
if(temp>tree[temp][0])//与已有结点比较大小,0位置放较小结点 
{
tree[temp][1] = tree[temp][0];
tree[temp][0] = i;
}
tree[temp][1] = i;
} 
}//输入for
//for(i=0;i<n;i++)
//	printf("%d:%d %d\n",i,tree[i][0],tree[i][1]);
Traverse(tree);
}
return 0;
}

 

这篇关于SJTU--1040 -- 二叉树层次遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---