[코테] 리트코드 트리 110. Balanced Binary Tree

110. Balanced Binary Tree

문제 링크

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

문제 설명

Given a binary tree, determine if it is height-balanced.

제한 사항

• The number of nodes in the tree is in the range [0, 5000].
• -10^4 <= Node.val <= 10^4

입출력 예 #1

1. Input : root = [3,9,20,null,null,15,7]
2. Output : true

입출력 예 #2

1. Input : root = [1,2,2,3,3,null,null,4,4]
2. Output : false

입출력 예 #3

1. Input : root = []
2. Output : true

문제 풀이

재귀를 이용하여 왼쪽 노드와 오른쪽 노드의 높이차를 구하여 균형 이진 탐색 트리인지 확인한다.

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)

            # 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
            if left == -1 or right == -1 or abs(left - right) > 1 :
                return -1
            return max(left, right) + 1

        return check(root) != -1