[알고리즘] 균형 이진 트리

균형 이진 트리

높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 말한다.

책 풀이

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBalanced(root: TreeNode) -> bool:
    def check(root):
        if not root:
            return 0

        left = check(root.left)
        right = check(root.right)

        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1

    return check(root) != -1