지름, 높이, 균형 이진 트리
두 값을 모두 반환하는 보조 함수를 사용해 한 번의 DFS로 트리의 지름과 높이를 계산한 뒤, 트리가 높이 균형을 이루는지 확인합니다.
지름, 높이, 균형 이진 트리은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
이진 트리의 높이
이진 트리의 height(또는 최대 깊이)는 루트에서 어떤 리프까지 이어지는 가장 긴 경로의 길이입니다. 재귀적으로 계산할 수 있습니다. 모든 노드의 height는 1 + max(height(left), height(right))이며, 널 노드의 기본값은 0입니다. 이 후위 순회 방식의 계산은 지름, 균형 확인, AVL 트리 회전의 기반이 되는 핵심 개념입니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4지름: 가장 긴 경로
이진 트리의 지름은 임의의 두 노드 사이에서 가장 긴 경로의 길이입니다(이 경로는 루트를 지날 수도 있고 지나지 않을 수도 있습니다). 경로의 길이는 간선 수로 측정합니다. 어떤 노드를 통과하는 지름은 height(left) + height(right)와 같습니다. 전체 지름은 트리의 모든 노드에서 계산한 이러한 값 중 최댓값입니다.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3한 번의 DFS로 지름 계산
순진한 방법은 각 노드에서 height()를 호출하므로 균형 잡힌 트리에서 O(n²)이 됩니다. 최적의 해법은 한 번의 DFS 순회에서 height를 계산하고 지름을 갱신합니다. 핵심은 재귀 함수 dfs()가 동시에 두 가지 역할을 한다는 점입니다. 부모에게 전달할 height를 반환하는 동시에 부수 효과로 전역 최대 지름을 갱신합니다. 이러한 이중 목적의 후위 순회 패턴은 많은 트리 문제에 등장합니다.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')균형 이진 트리 확인
이진 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이면 높이 균형 상태입니다. 무차별 대입 방식은 각 노드에서 height()를 호출하므로 O(n²)이 됩니다. 최적의 방법은 같은 한 번의 순회 기법을 사용합니다. ‘균형이 아님’을 나타내는 표식 값으로 -1을 반환하고 이를 위로 전달하여, 균형이 맞지 않는 노드를 발견하는 즉시 이후의 계산을 중단합니다.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # False표식 반환 값 패턴
표식 값(균형이 맞지 않으면 -1을 반환하거나 특수한 튜플을 반환하는 방식)은 DFS 보조 함수가 두 종류의 정보를 전달해야 할 때 사용하는 일반적인 패턴입니다. 즉, 계산된 결과와 제약 조건 위반 여부를 함께 전달합니다. 예외를 발생시키거나 전역 플래그를 사용하는 대신 반환 형식에 오류를 인코딩합니다. 이 방법은 깔끔하고 전역 상태를 피하며 다른 재귀 보조 함수와도 자연스럽게 결합됩니다.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2노드 수와 간선 수로 나타내는 지름
문제 설명을 주의 깊게 확인해야 합니다. LeetCode #543은 지름을 간선 수로 측정하지만, 일부 문제는 노드 수로 측정합니다. 노드 수가 필요하다면 어떤 노드를 통과하는 지름은 height(left) + height(right) + 1입니다(노드 자체를 위해 1을 더합니다). 간선 수가 필요하다면 +1을 생략합니다. 코딩하기 전에 항상 이 기준을 면접관에게 확인해야 합니다.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3경로 합: 임의의 루트에서 리프까지의 경로
경로 합 문제는 루트에서 리프까지 이어지는 경로 중 합이 목표값과 같은 경로가 있는지 묻습니다. DFS를 사용하고 내려갈 때마다 목표값에서 현재 노드의 값을 뺍니다. 리프에서는 남은 목표값이 해당 리프의 값과 같은지 확인합니다. 이는 매개변수로 남은 합을 전달하는 전위 DFS이며, 전형적인 하향식 재귀의 예입니다.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22최대 경로 합(어려운 변형)
최대 경로 합(LeetCode #124)은 훨씬 더 어렵습니다. 경로가 루트에서 리프까지로 제한되지 않고 어떤 노드에서든 시작하고 끝날 수 있으며, 값이 음수일 수도 있습니다. 각 노드에서 네 가지 경우를 고려합니다. 노드 자체, 노드 + 왼쪽 가지, 노드 + 오른쪽 가지, 노드 + 양쪽 가지입니다. 이 중 앞의 세 경우만 부모로 확장할 수 있고, 네 번째 경우는 전역 최댓값의 최종 후보가 됩니다.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7AVL 트리와 자체 균형 조정
AVL 트리는 삽입 및 삭제 작업 후 회전을 수행하여 높이 균형 속성을 유지하는 BST입니다. 각 노드는 균형 인자(height(right) - height(left))를 저장하며, 그 값은 {-1, 0, 1} 안에 있어야 합니다. 위반이 발생하면 단일 또는 이중 회전으로 O(1) 시간에 균형을 복원할 수 있으므로, 전체 height를 O(log n)으로 유지하고 모든 작업이 O(log n)임을 보장합니다.
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')대칭 이진 트리 확인
이진 트리는 자기 자신과 거울상 관계이면 대칭입니다. 축을 기준으로 대응하는 모든 노드 쌍의 값이 같고 서브트리도 서로 거울상인지 재귀적으로 확인합니다. is_mirror(left, right) 보조 함수를 정의하여 다음을 확인합니다. 둘 다 널이면 확인 완료, 하나만 널이면 불일치, 값이 같고 내부 및 외부 서브트리가 서로 거울상인지 확인합니다.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # False높이와 지름 통찰 결합
보조 함수가 높이를 반환하는 동시에 전역 결과를 갱신하는 한 번의 순회로 처리하는 후위 순회 패턴은 지름, 최대 경로 합, 균형 확인, 양호한 노드 개수 세기 등 다양한 문제에 재사용할 수 있습니다. 항상 다음과 같이 자문해 보십시오. 「부모 노드가 각 자식 노드에서 필요로 하는 정보는 무엇인가?」 그것이 반환값입니다. 「이 노드에서만 수행되는 계산은 무엇인가?」 그 계산이 전역 답을 갱신합니다. 이러한 분해가 어려운 트리 문제를 해결하는 핵심 능력입니다.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2빠른 확인
이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
수업 요약
이 수업에서는 재귀적 후위 순회 DFS를 사용한 높이 계산, 두 가지 역할을 하는 DFS 보조 함수를 이용해 한 번의 O(n) 순회로 수행하는 지름 계산, 그리고 조기 종료용 특수 값을 활용한 균형 확인을 배웠습니다. 다음에는 경로 합 문제와 최소 공통 조상을 다룹니다.
자주 묻는 질문
“지름, 높이, 균형 이진 트리” 강의는 무료인가요?
네 — “지름, 높이, 균형 이진 트리” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“지름, 높이, 균형 이진 트리”에서 뭘 배우나요?
두 값을 모두 반환하는 보조 함수를 사용해 한 번의 DFS로 트리의 지름과 높이를 계산한 뒤, 트리가 높이 균형을 이루는지 확인합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“지름, 높이, 균형 이진 트리” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TreeNode 클래스와 레벨 순서 BFS
- 중위, 전위, 후위 DFS
- 지름, 높이, 균형 이진 트리
- 경로 합과 최소 공통 조상