← 전체 회차
A-049● Day 492026.06.24easyleetcode #110neetcode150

균형 이진 트리

#tree#depth-first-search#binary-tree
↗ leetcode #110 · balanced-binary-tree
01

문제

· problem
P.049

균형 이진 트리

↗ leetcode #110

이진 트리가 주어졌을 때, 해당 트리가 높이 균형(height-balanced)을 만족하는지 판단하세요. 높이 균형 트리는 모든 노드에서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이 차이의 절댓값이 1 이하인 이진 트리입니다.

제약
  • · The number of nodes in the tree is in the range [0, 5000].
  • · -10⁴ ≤ Node.val ≤ 10⁴
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,9,20,null,null,15,7]
true
example 2input → output
[1,2,2,3,3,null,null,4,4]
false
example 3input → output
[]
true
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    높이 균형이란 무엇을 의미하나요?
  • ☐
    빈 트리는 균형 잡혀 있나요?
  • ☐
    단일 노드는 균형 잡혀 있나요?
  • ☐
    모든 부분 트리가 균형을 만족하면 전체 트리도 균형을 만족하나요?
  • ☐
    한 번의 순회로 답을 구할 수 없고 여러 번 높이를 계산해야 하나요?
  • ☐
    완전 이진 트리(complete binary tree)는 항상 균형을 만족하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 기저 사례: 빈 노드 확인│ 중첩
○
if not root:
○
if not root.left and not root.right:
○
if root == None:
step 2· 기저 사례: 반환값 [균형, 높이]│ 중첩
○
return [True, 0]
○
return [True, 1]
○
return (True, 0)
step 3· 재귀 호출: 왼쪽과 오른쪽 부분 트리 탐색│ 중첩
○
left, right = dfs(root.left), dfs(root.right)
○
left, right = dfs(root.right), dfs(root.left)
○
if dfs(root.left) and dfs(root.right):
step 4· 균형 검증: 세 가지 조건 확인│ 중첩
○
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
○
balanced = abs(left[1] - right[1]) <= 1
○
balanced = left[0] and right[0] and abs(left[1] - right[1]) < 1
step 5· 현재 노드 반환: [균형, 높이 업데이트]│ 중첩
○
return [balanced, 1 + max(left[1], right[1])]
○
return [balanced, 1 + left[1] + right[1]]
○
return [balanced, max(left[1], right[1])]
step 6· 최종 반환: 루트의 균형 여부 추출
○
return dfs(root)[0]
○
return dfs(root)[1]
○
return dfs(root)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
9
        def dfs(root):
10
            if not root:
11
                return [True, 0]
12
13
            left, right = dfs(root.left), dfs(root.right)
14
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
15
            return [balanced, 1 + max(left[1], right[1])]
16
17
        return dfs(root)[0]
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,9,20,null,null,15,7]
→
true
case 2
[1,2,2,3,3,null,null,4,4]
→
false
case 3
[]
→
true
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.