Hackerrank Day 22 Binary Search Trees

알고리즘 연습 사이트

www.hackerrank.com

Day 22:Binary Search Trees

2진 트리(Binary Trees)

 2진 트리의 가장 깊은 노드까지의 거리 (height)를 계산하는 메소드를 구현한다. 
즉 root 노드로부터 가장 먼 자식 노드까지의 거리를 구하는 것이다. 
 2진 트리는 right, left 노드 2개를 갖거나 둘 중의 하나의 자식만 갖거나 아예 자식이 존재하지 않는다.(leaf)

 오늘 문제의 키 포인트는 인자로 들어오는 root노드의 자식 노드를 검사할 때, right, left 자식 노드가 각각 존재하는지 한번에 체크를 해야한다.

 각 사이드의 자식 노드가 존재한다면 해당 높이변수에 1을 더하고 그의 하위자식노드를 인자로 넘겨주어 재귀호출을 한다. 
 주의깊게 살펴봐야 할 부분은 return 부분인데 이곳에서 max height 을 처리한다.

 자식노드가 몇 개가 달려있건간에 자식노드가 존재하지 않을 때까지 재귀호출 되어 결국 마지막 leaf노드에 도달하였을 때 right과 left중 큰 쪽의 height 을 리턴한다. (깊이가 깊은 것이 2개가 있다고 해도 어쨌든 둘중의 하나를 리턴한다.) 그러면 재귀호출이 된 지점으로 반환되면서 결국 가장 최초의 getHeight 메소드 호출의 리턴에서 가장 큰 height값을 구할 수 있다.

 2진 트리가 어떻게 구성되고 특징이 무엇인지 이해하여야 풀 수 있었던 문제였다.

public static int getHeight(Node root){
        int heightLeft = 0;
        int heightRight = 0;
        
        if(root.left !=null){
            heightLeft = 1 + getHeight(root.left);
        }
        if(root.right !=null){
            heightRight = 1 + getHeight(root.right);
        }
        return heightLeft > heightRight ? heightLeft : heightRight; 
}