greentea31's Note

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

풀이 과정

주어진 이진 트리가 균형잡힌 이진 트리인지 확인하는 문제이다.

균형잡힌 이진 트리란, 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가 2보다 작은 이진 트리를 의미한다.

재귀를 활용해 리프 노드를 탐색하고, 리프 노드에서 현재 노드까지의 거리를 기록하게끔 코드를 작성하였다. 현재 노드에서 왼쪽 자식을 통해 탐색 가능한 리프 노드까지와의 거리와, 오른쪽 자식을 통해 탐색 가능한 리프 노드까지의 거리가 1 이상 차이가 나는 노드가 존재하면, 그 트리는 균형잡힌 이진 트리가 아니다.

소스 코드

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)
            
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return max(left, right) + 1
        
        return check(root) != -1