[LeetCode 해석 및 풀이] 110. Balanced Binary Tree (균형 잡힌 이진트리)

LeetCode 문제 해석 및 풀이 방법

 

문제 110. Balanced Binary Tree (균형 잡힌 이진트리)

바로가기

 

문제 설명

영문

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

한글

이진 트리가 주어지면, 높이-균형이 잡혀있는지 결정하십시오

 

높이-균형 이진트리는 모든 노드의 자식 트리의 높이차가 1보다 크지 않는 트리를 뜻합니다.

 

제한조건

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

 

입출력 예

입력	출력
[3,9,20,null,null,15,7]	true
[1,2,2,3,3,null,null,4,4]	false
[]	true

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def treeDepthBalanced(node):
            if not node:
                return (0, True)
            
            l_depth, l_isbalanced = treeDepthBalanced(node.left)
            r_depth, r_isbalanced = treeDepthBalanced(node.right)

            isbalanced = l_isbalanced and r_isbalanced and abs(l_depth-r_depth) <= 1
            depth = max(l_depth, r_depth) + 1

            return (depth, isbalanced)
        
        _, isbalanced = treeDepthBalanced(root)

        return isbalanced

이진 트리의 최대 깊이를 재귀로 구한 후, 높이를 비교하고 상위 노드 비교시에 쓰면 된다.

 

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        isbalanced = True

        def treeDepthBalanced(node):
            if not node:
                return 0

            nonlocal isbalanced

            l_depth = treeDepthBalanced(node.left)
            if not isbalanced:
                return

            r_depth = treeDepthBalanced(node.right)
            if not isbalanced:
                return

            if not abs(l_depth-r_depth) <= 1:
                isbalanced = False
                return 

            depth = max(l_depth, r_depth) + 1

            return depth
        
        treeDepthBalanced(root)

        return isbalanced

 

다음과 같이 전역변수를 이용해줘도 된다.