1 package test;  2 import java.util.ArrayList;  3 import java.util.Iterator;  4 import java.util.LinkedList;  5 import java.util.Queue;  6 import java.util.Scanner;  7 class Node{  8       9     public Node(int father, int child) { 10         this.father = father; 11         this.child = child; 12     } 13     int father; 14     int child; 15 } 16  17 public class tree { 18     /**** 19      * 层次遍历的思想，队列实现，按层添加到队列，末尾入队-1； 20      */ 21     public static int deep(int n,ArrayList<Node> tree){ 22         int count=0; 23         int j=0;//记录操作了多少个结点； 24         if(n<=0){ 25             return 0; 26         }else if(n==1){ 27             return 2; 28         }else{ 29             Queue<Integer> queue=new LinkedList<Integer>(); 30             queue.offer(0); 31             j++; 32             queue.offer(-1);// 33             boolean flag=false;//判断是否到尾结点； 34             while(!queue.isEmpty()){ 35 //　　　　　　　　printdata(queue); 36                 Integer data=http://www.mamicode.com/queue.poll(); 37 //                System.out.println(); 38 //                System.out.println("data:"+data); 39 //                System.out.println(); 40                 if(j==n&&flag==false){ 41                     queue.offer(-1); 42                     flag=true; 43                 }else if(data=http://www.mamicode.com/=-1){     44                     if(flag){ 45                         count++; 46                     }else{ 47                         queue.offer(-1); 48                         count++; 49                     }                     50                 }else{ 51                     for(int i = 0;i < tree.size(); i ++){ 52                         if(tree.get(i).father==data){ 53                             queue.offer(tree.get(i).child); 54                             j++; 55                         } 56                     }                     57                 } 58             } 59              60         } 61  62         return count; 63     } 64     public static void printdata(Queue<Integer> queue){ 65         for(Iterator it2 = queue.iterator();it2.hasNext();){ 66             System.out.println("Q:"+it2.next()); 67        } 68     } 69  70     public static void main(String[] args) { 71         // TODO Auto-generated method stub 72         Scanner in =new Scanner(System.in); 73 //        while(in.hasNext()){ 74             int n=in.nextInt(); 75             ArrayList<Node> tree =new ArrayList<Node>(); 76             for(int i=0;i<n-1;i++){ 77                 int father=in.nextInt(); 78                 int child=in.nextInt(); 79                 Node node=new Node(father,child); 80                 tree.add(node);            } 81             System.out.println(deep(n,tree)); 82 //        } 83     } 84  85 } 86 /** 87  *  88  *  89 9 90 0 1 91 0 2 92 1 3 93 1 4 94 2 5 95 2 6 96 3 7 97 3 8 98  99 5100 0 1101 0 2102 1 3103 1 4104 **/

90 10 21 31 42 52 63 73 84