求树的高度

拼搏现实的明天。 2022-05-28 04:29 108阅读 0赞

题目：树的高度

时间限制：C/C++语言 1000MS；其他语言 3000MS   
内存限制：C/C++语言 65536KB；其他语言 589824KB   
题目描述：   
现在有一棵合法的二叉树，树的节点都是用数字表示，   
现在给定这棵树上所有的父子关系，求这棵树的高度

输入   
输入的第一行表示节点的个数n（1<=n<=1000，节点的编号为0到n-1）组成，   
下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出   
输出树的高度，为一个整数

样例输入   
5   
0 1   
0 2   
1 3   
1 4

样例输出

一、方法一

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            int nodeNum = sc.nextInt();
            Map<Integer, Integer> dict = new HashMap<>();
            int father, son ;
            int highest = 0;
    
            if(nodeNum == 1) {
                System.out.print(1);
                return;
            }
            for (int i=0; i< nodeNum -1; i++){
                father = sc.nextInt();
                son = sc.nextInt();
                dict.put(son, father);　// 反序存入
            }
            int count;
            for(Integer key : dict.keySet() ){
                count = １;
                //  循环获得每个节点的高度
                while(dict.containsKey(key)){
                    count ++;
                    key = dict.get(key);
                }
                if(highest < count) highest = count;
            }
            System.out.print(highest);
        }
    }

二、方法二

import java.util.Scanner;
     
    public class Main{
        public static void main(String[] args) {
            Scanner in  = new Scanner(System.in);
            int n = in.nextInt();
            if(n<3){
                System.out.println(n);
            }
            else{
                int[] height = new int [n];
                int[] binary = new int[n];
                height[0] = 1;
                int max = 0;
                for(int i = 0;i<n-1;i++){
                    int parent = in.nextInt();
                    int child = in.nextInt();
                    binary[parent] += 1;
                    if(binary[parent] < 3){
                        height[child] = height[parent]+1;
                    }
                    max = Math.max(max, height[child]);
                }
                System.out.println(max);
            }
        }
    }