5-3: 트리의 높이

트리의 높이

 

문제

---

트리의 높이는 루트로부터 가장 멀리 떨어진 노드와의 거리로 정의된다. 예를 들어, 아래의 트리에서 0번 노드가 루트라고 하면, 7번 노드까지의 거리가 가장 멀고, 그 거리는 3이다. 따라서 이 트리의 높이는 3이 된다.

트리가 주어질 때, 그 트리의 높이를 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 트리의 노드 개수 n, 그리고 루트노드의 번호 r이 주어진다. ( 1 ≤ r ≤ n ≤ 100 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 a번 노드와 b번 노드가 연결되어 있다는 뜻이다.  

출력

---

트리의 높이를 출력한다.

 

예제 입력

8 0
0 1
0 2
1 3
1 4
1 5
2 6
6 7

예제 출력

3

import java.util.ArrayList;
import java.util.Scanner;

public class TreeHeight {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int r = sc.nextInt();

        TreeNode[] nodes = new TreeNode[N];
        int[] heights = new int[N];

        for (int i=0; i<N-1; i++){
            int curData = sc.nextInt();
            int childData = sc.nextInt();

            if (nodes[curData] == null) {
                TreeNode node = new TreeNode(curData);
                nodes[curData] = node;
            }

            if (nodes[childData] == null) {
                TreeNode node = new TreeNode(childData);

                nodes[childData] = node;
                nodes[curData].children.add(nodes[childData]);
            }

        }

        TreeNode root = nodes[r];


//    TreeNode lca = lca(nodes[0], nodes[X], nodes[Y]);
        System.out.println(getHeight(root)-1);
//    System.out.println(lca.data);


    }

    private static int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int maxChildHeight = 0;
        for (TreeNode child : node.children){
            int childHeight = getHeight(child);
            if (childHeight >= maxChildHeight){
                maxChildHeight = childHeight;
            }
        }
        return 1+maxChildHeight;
    }


    private static TreeNode lca(TreeNode root, TreeNode x, TreeNode y) {
        if (root == null) {
            return null;
        }
        if (root == x || root ==y){
            return root;
        }

        TreeNode[] lcaNodes = new TreeNode[root.children.size()];
        int index = 0;
        int count = 0;
        TreeNode temp = null;
        for (TreeNode child : root.children){
            lcaNodes[index] = lca(child, x, y);
            if (lcaNodes[index] != null){
                count++;
                temp = lcaNodes[index];
            }
            index++;
        }

        if (count >=2) return root;

        return temp;
    }


    public static class TreeNode{
        int data;
        //        TreeNode left;
////        TreeNode right;
        ArrayList<TreeNode> children;

        public TreeNode(int data){
            this.data = data;
            children = new ArrayList<>();
        }
    }
}