LeetCode 110. Balanced Binary Tree with Python

https://leetcode.com/problems/balanced-binary-tree/description/

이 문제 또한 어려워서 못풀었다..
사실 balanced binary tree 가 뭔지 잘 몰라서 엄청 해맸던 거 같다.
루트 기준으로 생각했기 때문에

이건 balanced인데

이건 balanced가 아니라는게 뭔말이야 대체 하고 한참을 고민했더라는,,,,
얘 또한 루트 기준으로 balanced가 아니가 각 노드 기준으로 balanced였다,,ㅎ
결국 각 노드 기준으로 left가 없는데 right가 2개라던가 right가 없는데 left가 2개와 같은 상황이 있으면 안됐던것!
(한쪽으로 치우친 트리를 편향 이진 트리라고 한다. 성능면에서 최악이라고 한다. 찾을 때까지 내려가야하기 때문 O(N))
높이 균형을 매번 맞추는 AVL 트리가 대표적인 자가 균형 이진 탐색 트리라고 한다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(root):
            if not root:
                return 0

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

            # 이미 불균형이 온 쪽이 있거나 차이가 2 이상 나면 -1 반환
            if left == -1 or right == -1 or abs(left-right) > 1:
                return -1

            # 가장 긴 루트 + 1(현재 위치까지)
            return max(left, right) + 1

        return check(root) != -1

제일 밑까지 내려갔다가 올라오면서 왼쪽 오른쪽의 레벨 차이를 구하고 2이상 나게된다면 -1를 리턴함으로써 얘 불균형이에요를 알렸다(?)
그리고 -1이 리턴된다면 이미 아래에서 불균형이 왔단 뜻임으로 계속해서 -1을 리턴하게 되고
결국 재귀가 끝날때까지 -1이라면 불균형이라는 뜻이었다!