4.4 균형 확인

문제: 이진트리가 균형이 잡혀있는지 확인하는 함수를 작성하라.

0) 균형 잡힌 트리란? 

모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가

최대 하나인 트리를 의미한다.

1) 풀이 핵심 - 재귀사용

2) 개선 전 - O(N log N)

루트부터 시작해서 높이를 구한후 

균형 판단하고

다시 반복적으로 루트 아래로 내려가면서 균형판단

3) 개선 후 - O(N)

루트노두의 두서브 트리의 높이의 차를 한번만 구해오면서

중간에 균형 판단 

4) 공통점 - (최악의경우)균형판단의 횟수는 같음

5) 차이점 - 높이를 한번 구하냐  vs 높이를 계속 구하냐