本帖最後由 李泳霖 於 2022-4-30 10:05 編輯
承 樹狀圖 (一) - 無分岔點,以類似的解題技巧,完成下列三個有分岔點的範例練習。
範例輸入一
6
3 5
0 1
3 4
1 2
1 3
範例輸出一
根節點: 0
葉節點: 2 4 5
最深距離: 3
範例輸入二
9
7 6
2 4
3 0
7 1
6 8
2 5
3 2
0 7
範例輸出二
根節點: 3
葉節點: 1 4 5 8
最深距離: 4
範例輸入三
10
9 1
2 0
7 4
8 3
9 6
9 8
7 2
7 9
5 7
範例輸出三
根節點: 5
葉節點: 0 1 3 4 6
最深距離: 4
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- public class Ch01 {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- String raw[];
- Node[] node;
- int root,n;
- ArrayList<Integer>leaf=new ArrayList<Integer>();
- Ch01()throws Exception{
- n=Integer.parseInt(br.readLine());
- node=new Node[n];
- for(int i=0;i<n;i++)
- node[i]=new Node();
- for(int i=0;i<n-1;i++){
- raw=br.readLine().split(" ");
- int p=Integer.parseInt(raw[0]);
- int c=Integer.parseInt(raw[1]);
- node[c].parent=p;
- node[p].child.add(c);
- }
- System.out.println("每個節點的父");
- for(int i=0;i<n;i++)
- System.out.println("node["+i+"]的parent為"+node[i].parent);
- System.out.println("每個節點的子");
- for(int i=0;i<n;i++)
- System.out.println("node["+i+"]的child為"+node[i].child);
- }
- class Node{
- int parent=-1;
- int h=0;
- ArrayList<Integer>child=new ArrayList<Integer>();
- }
- public static void main(String[] args) throws Exception{
- new Ch01();
- }
- }
複製代碼 |