균형 이진 트리

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

Balanced Binary Tree - LeetCode

 이진 트리가 높이 균형인지 판단하라. 

 

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

 높이 균형은 매우 중요한 개념이다. 균형이 맞아야 효율적으로 트리를 구성할 수 있으며, 탐색 또한 더 효율적으로 처리할 수 있기 때문이다. 

 

 먼저 재귀 호출로 리프 노드까지 내려간다. 맨 마지막 노드에 이르면 각각 left=0, right=0을 리턴하도록 구성했다.

 

 left와 right가 모두 0이라면 차이가 1보다 크지 않으므로 max(left,right)+1로 1을 리턴하게 된다. 이런 식으로 점점 1씩 증가하는 형태가 리턴된다.

 

 예제에서 false로 처리된 것을 살펴보자.

리프부터 높이를 쌓아 올려 좌우 비교

 루트 1의 오른쪽 자식 노드인 2는 더 이상 자식이 없으므로 값은 1을 받게 된다. 그 왼쪽, 즉 형제 노드는 3이므로 높이 차이가 1을 초과하므로, -1을 리턴받는다. 즉 루트는 -1이 된다. 이렇게 한번 -1이 되면 더 이상 회복이 되지 않는다. 만약 부모 노드가 또 있다 해도 그 오른쪽 노드는 어떠한 경우에도 1이상의 값을 갖게 될 것이므로 계속해서 높이 차이가 1을 초과한다. 때문에 마찬가지로 -1을 리턴받는다. 즉 양쪽 자식 노드 중 어느 하나가 -1이 되는 경우에는 계속해서 -1을 리턴하게 되며, 각 서브트리 높이 차이가 한 번이라도 1을 초과하는 경우 -1이 할당되며 계속해서 부모 노드로 -1을 리턴하다 최종적으로 False를 리턴하게 된다.

 

# 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
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