4.4 균형확인

문제

이진 트리가 균형 잡혀있는지 확인하는 함수를 작성하라. 이 문제에서 균형 잡힌 트리란 모든 노드에 대해서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미한다. 

 

해결법

재귀적으로 각 노드까지의 높이를 확인하며 1이상의 차이가 나는지 확인하고, 1 이상의 차이가 나지 않는다면 높이를 반환해 나가며 균형이 잡혀있는지 확인한다. 

def chkHeight(root):
    if root is None :
        return -1
    
    left = chkHeight(root.left)
    if left == float("Inf") : return float("Inf")

    right = chkHeight(root.right)
    if right == float("Inf") : return float("Inf")

    heightdiff = abs(left-right)
    if heightdiff > 1 :
        return float("Inf")
    else :
        return max(left, right) +1

def Solution(root):
    return chkHeight(root) != float("Inf")