[HackerRank] Tree: Height of a Binary Tree

Binary Tree, 이진트리의 height 높이는 트리의 root와 가장 멀리 있는 leaf 사이 edge들의 수이다.

고로 요 녀석의 트리의 높이는 2가 되는 것이다.

 

Q. 트리의 노드 수를 int타입의 n으로 입력받고, 다음 줄에는 n개의 node[i]. data가 정수 타입으로 입력되는데, 최종적으로 이진트리의 높이를 int 타입으로 반환해야 한다. 이를 위해 height 함수를 완성하자! 

예를 들어, 위와 같은 트리가 Input으로 들어간다면, 트리의 height는 3이 된다.

 

main 메소드와 insert 메서드가 있으므로 트리는 이미 생성되어 있으니 트리의 높이를 구하는 height 메서드만을 완성하면 된다. 

public static int height(Node root) {
      	
        int leftHeight = 0;
        int rightHeight = 0;

        if (root.left != null) {
            leftHeight = 1 + height(root.left);
        }

        if (root.right != null) {
            rightHeight = 1 + height(root.right);
        }

        if( leftHeight > rightHeight ) return leftHeight;
        else return rightHeight;
                
    }

루트 기준 왼쪽과 오른쪽에 있는 노드들에서의 높이를 구해서 더 큰 쪽의 값을 height으로 인정하여 반환하도록 한다.

사실 엄청 간단하게는 ``` Math.max(height(root.left), height(root.right)) + 1 ``` 로 바로 구할 수도 있다.