Skip to main content

110. Balanced Binary Tree

문제​

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

예제 입출력​

img

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

You can read the full description here.

풀이 1​

접근법​

  1. 후위 순회를 하면서 리프노드로부터의 거리를 매깁니다.
  2. 좌우 자식 노드의 값이 2 이상 차이나는 경우가 존재하면 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:
        result = True

        def postorder(node: Optional[TreeNode]) -> int:
            nonlocal result
            if node is None:
                return -1
            left = postorder(node.left)
            right = postorder(node.right)

            if (abs(left - right) > 1):
                result = False

            return max(left, right) + 1

        postorder(root)

        return result

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)

책에 있는 풀이​

info

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2​

접근법​

  1. 풀이 1과 유사합니다.

image

구현 코드​

class Solution:
    def isBalanced(self, root: 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

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)