北邮 BOJ 133 二叉树的层数

思路：

都告诉1 是根节点了，直接从1往下搞，队列层序遍历

解答：

package bupt;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
*@author:Totoro
*@createDate:2020年3月18日下午7:44:15
*/
public class 二叉树的层数
	{

	public static point[] tree;
	public static int now_n;
	public static int[] is_creat=new int[105];
	
	public static void main(String[] args)
		{
		Scanner cin=new Scanner(System.in);
		int t,n,m,a,b;
		t=cin.nextInt();
		for(int tt=1;tt<=t;++tt)
			{
			n=cin.nextInt();
			m=cin.nextInt();
			tree=new point[m];
			Arrays.fill(is_creat,-1);
			now_n=0;
			while(n--!=0)
				{
				a=cin.nextInt();
				b=cin.nextInt();
				if(is_creat[b]==-1)
					{
					is_creat[b]=now_n;
					tree[now_n++]=new point(b);
					}
				int fa_index=is_creat[b];
				if(tree[fa_index].lc==-1)
					tree[fa_index].lc=now_n;
				else
					tree[fa_index].rc=now_n;
				tree[now_n]=new point(a);
				is_creat[a]=now_n++;
				
				}
			
			for(int i=0;i<now_n;++i)
				if(tree[i].v==1)
					{
					Queue<Integer> qe=new LinkedList<Integer>();
					qe.offer(i);
					System.out.println("Q"+tt+":");
					go(qe);
					break;
					}
			
			}
		}
	
	public static void go(Queue<Integer> qe)
		{
		Queue<Integer> qee=new LinkedList<Integer>();
		int x;
		point p;
		while(qe.peek()!=null)
			{
			x=qe.poll();
			p=tree[x];
			System.out.print(p.v);
			if(p.lc!=-1)
				qee.offer(p.lc);
			if(p.rc!=-1)
				qee.offer(p.rc);
			if(qe.peek()!=null)
				System.out.print(" ");
			else
				break;
			}
		System.out.println();
		if(qee.peek()!=null)
			go(qee);
		}
	
	public static class point
		{
		int lc,rc;
		int v;
		public point(int v)
			{
			this.v=v;
			lc=-1;
			rc=-1;
			}
		}

	}