[알고리즘] Leetcode #110 균형 이진 트리 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

 

입출력 예

Example 1:

 

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

 

Example 2:

 

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

Example 3:

Input: root = [] Output: true

 

Constraints

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

 

Code

# 재귀 구조로 높이 차이 계산
def isBalanced(self, root):
    def check(root):
        if not root:
            return 0
        
        left = check(root.left)
        right = chech(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

이진트리에서 높이 균형은 효율적인 트리 구성에 매우 핵심적이라고 한다. 입력으로 받은 트리가 균형 트리인지 확인하기 위해 가장 아래 노드부터 0으로 시작해 왼쪽, 오른쪽 노드의 깊이가 얼마나 차이나는지 확인할 수 있다. 이때, 균형 트리의 정의에 따라 양쪽 자식 노드에 계산된 값의 차이가 1 초과가 되면, -1를 return하도록 했는데, 한 번 -1을 가진 노드가 생기면 그 트리는 균형 트리가 될 수 없다.