PricingLoginStart free
DSA Interview Prep · 강의

경로 합과 최소 공통 조상

재귀적으로 내려가며 일반 이진 트리의 root-to-leaf path sum, all-paths-sum, lowest-common-ancestor를 해결합니다.

레슨 4/413개 단계

경로 합과 최소 공통 조상은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

루트에서 리프까지의 경로 합

경로 합 문제는 어떤 루트에서 리프까지의 경로 합이 목표값과 같은지 묻습니다. 각 노드의 값을 빼면서 남은 목표값을 재귀 호출에 전달하십시오. 리프에서는 남은 값이 해당 리프의 값과 같은지 확인합니다. 이렇게 하면 명시적인 경로 목록을 유지할 필요가 없으므로 공간을 효율적으로 사용하면서도 코드가 간결해집니다. 예외 상황으로, 빈 트리에는 경로가 없으므로 즉시 False를 반환해야 합니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:  # leaf
        return root.val == target
    remain = target - root.val
    return (has_path_sum(root.left, remain) or
            has_path_sum(root.right, remain))

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

루트에서 리프까지의 모든 경로

모든 경로를 나열하려면 현재까지의 경로 목록을 유지해야 합니다. 각 재귀 호출에서 현재 노드의 값을 목록에 append하고, 자식 노드를 재귀적으로 탐색한 다음 돌아올 때 pop합니다(되돌아가기). 리프에서는 현재 경로의 스냅샷인 list(path)를 기록합니다. 선택하고, 재귀 호출하고, 선택을 취소하는 이 패턴은 트리에서 백트래킹의 기반입니다.

def all_path_sums(root, target):
    results = []

    def dfs(node, path, remaining):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            results.append(list(path))  # snapshot
        else:
            dfs(node.left, path, remaining - node.val)
            dfs(node.right, path, remaining - node.val)
        path.pop()  # backtrack

    dfs(root, [], target)
    return results

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22))  # [[5,4,11,2]]

경로 합 III: 모든 경로, 모든 노드

경로 합 III(LeetCode #437)는 경로의 시작과 끝이 어디든 될 수 있을 때 목표값과 같은 합을 만드는 경로의 수를 셉니다. 즉, 루트에서 리프까지의 경로로만 제한되지 않습니다. 완전 탐색 방식의 시간 복잡도는 O(n²)로, 각 노드에서 DFS를 실행합니다. 최적의 O(n) 방법은 접두사 합 해시 맵을 사용하는 것입니다. 누적 합을 추적하면서 current_sum - target이 이전에 등장한 횟수를 세며, 이는 부분 배열 합 문제의 접근법과 같은 원리입니다.

def path_sum_iii(root, target):
    prefix_counts = {0: 1}

    def dfs(node, running_sum):
        if not node:
            return 0
        running_sum += node.val
        count = prefix_counts.get(running_sum - target, 0)
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
        count += dfs(node.left, running_sum)
        count += dfs(node.right, running_sum)
        prefix_counts[running_sum] -= 1  # backtrack
        return count

    return dfs(root, 0)

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8))  # 3

최소 공통 조상이란 무엇인가

이진 트리에서 두 노드 p와 q의 최소 공통 조상(LCA)은 p와 q를 모두 자손으로 가지는 가장 깊은 노드입니다(노드 자신도 자신의 자손으로 간주할 수 있습니다). LCA는 「두 노드 사이의 거리」, 「두 노드 사이의 경로」, BST 범위 질의와 같은 문제에 등장합니다. LCA를 이해하는 것은 중급 트리 문제를 해결하는 데 필수적입니다.

#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4
# LCA(5, 1) = 3  (root)
# LCA(5, 4) = 5  (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')

LCA 재귀 알고리즘

우아한 재귀 LCA 해법은 p 또는 q이거나, 두 노드를 모두 자신의 하위 트리에 포함하는 첫 번째 노드를 반환합니다. 현재 노드가 p 또는 q라면 해당 노드를 반환합니다. 그렇지 않으면 왼쪽과 오른쪽을 재귀적으로 탐색합니다. 양쪽에서 모두 널이 아닌 결과가 반환되면 현재 노드가 LCA입니다. 한쪽에서만 널이 아닌 결과가 반환되면 그 결과를 위로 전달합니다. 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(h)입니다.

def lowest_common_ancestor(root, p, q):
    # Base case: empty or found one of the targets
    if not root or root == p or root == q:
        return root
    # Search both subtrees
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    # If both sides found something, this node is the LCA
    if left and right:
        return root
    # Otherwise, return whichever side found something
    return left if left else right

root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right  # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val)  # 3

노드가 자기 자신의 조상일 수 있을 때의 LCA

중요한 예외 상황은 p가 q의 조상인 경우(또는 그 반대)입니다. 이때 LCA는 p 자신입니다. 재귀 알고리즘은 이 경우를 자동으로 처리합니다. p에 도달하면 p의 하위 트리를 살펴보지 않은 채 p를 즉시 반환합니다. 부모 노드는 한쪽에서 p가 반환되고 다른 쪽에서는 널이 반환된 것을 확인하므로, p를 LCA로서 위쪽으로 전달합니다. LCA를 구현할 때는 테스트에서 이 경우를 반드시 확인하십시오.

# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)

p = root.left     # node 5
q = root.left.left  # node 6

lca = lowest_common_ancestor(root, p, q)
print(lca.val)  # 5 (p itself is the LCA)

부모 포인터를 사용하는 LCA

각 노드에 부모 포인터가 있다면 LCA 문제는 「두 연결 리스트의 교차점」 문제로 단순화됩니다. p의 조상들을 집합에 모은 다음, q에서 시작해 위로 이동하면서 해당 집합에 포함된 노드를 찾습니다. 이 방식은 시간 O(h), 공간 O(h)이며, 노드 구조를 직접 정하고 부모 참조를 저장할 수 있는 시스템 설계 면접에서 자주 사용됩니다.

class NodeWithParent:
    def __init__(self, val, parent=None):
        self.val = val
        self.parent = parent
        self.left = None
        self.right = None

def lca_with_parent(p, q):
    ancestors = set()
    # Collect all ancestors of p
    node = p
    while node:
        ancestors.add(node)
        node = node.parent
    # Walk up from q until we hit a known ancestor
    node = q
    while node:
        if node in ancestors:
            return node
        node = node.parent
    return None

print('With parent pointers: O(h) time and space')

이진 탐색 트리에서의 LCA

BST에서는 순서 규칙에 따라 각 노드가 어느 하위 트리에 있는지 알 수 있으므로 LCA를 더 간단하게 구할 수 있습니다. p와 q가 모두 현재 노드보다 작으면 LCA는 왼쪽 하위 트리에 있습니다. 둘 다 더 크면 LCA는 오른쪽 하위 트리에 있습니다. 그렇지 않으면 현재 노드가 두 노드를 가르므로 현재 노드가 LCA입니다. 따라서 균형 잡힌 BST에서는 이 문제를 O(log n)으로 줄일 수 있습니다.

def lca_bst(root, p, q):
    if not root:
        return None
    if p.val < root.val and q.val < root.val:
        return lca_bst(root.left, p, q)  # both in left
    if p.val > root.val and q.val > root.val:
        return lca_bst(root.right, p, q)  # both in right
    return root  # split point = LCA

# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

print('BST LCA: O(log n) for balanced trees')

두 노드 사이의 거리

트리에서 두 노드 사이의 거리는 두 노드를 연결하는 경로에 있는 간선의 수와 같습니다. 이는 LCA를 사용해 다음과 같이 직접 계산할 수 있습니다. distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)) 먼저 LCA를 찾은 다음 각 노드의 깊이를 세십시오. 적절한 보조 함수를 사용하면 시간 O(n), 공간 O(h)에 실행됩니다.

def find_depth(root, target, depth=0):
    if not root:
        return -1
    if root == target:
        return depth
    left = find_depth(root.left, target, depth + 1)
    if left != -1:
        return left
    return find_depth(root.right, target, depth + 1)

def node_distance(root, p, q):
    lca = lowest_common_ancestor(root, p, q)
    # depth from LCA to p and q
    dp = find_depth(lca, p)
    dq = find_depth(lca, q)
    return dp + dq

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right))  # 2

루트에서 리프까지의 최대 합 경로

루트에서 리프까지의 최대 합 경로는 루트부터 현재 노드까지의 누적 합을 추적합니다. 리프에 도달하면 전역 최댓값과 비교합니다. 이는 현재 경로 합을 매개변수로 전달하는 전위 순회 DFS입니다. 일반적인 최대 경로 합과 달리 이 방법은 루트에서 리프까지의 경로로 제한되므로 더 간단합니다. 임의의 두 노드를 잇는 경로까지 고려할 필요가 없습니다.

def max_root_to_leaf_sum(root):
    if not root:
        return float('-inf')
    best = [float('-inf')]

    def dfs(node, running):
        running += node.val
        if not node.left and not node.right:  # leaf
            best[0] = max(best[0], running)
            return
        if node.left:
            dfs(node.left, running)
        if node.right:
            dfs(node.right, running)

    dfs(root, 0)
    return best[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root))  # 1+2+5 = 8

루트에서 리프까지의 수 합

루트에서 리프까지의 수 합(LeetCode #129)은 각 루트-리프 경로를 십진수로 간주합니다(예: 경로 1→2→3은 123을 나타냅니다). 그리고 그러한 수들의 합을 구합니다. current_number * 10 + node.val을 재귀 호출에 전달하면서 수를 구성하십시오. 각 리프에서는 완성된 수를 전체 합에 더합니다. 이는 누적 상태를 아래로 전달하는 전위 순회 DFS를 깔끔하게 보여 주는 예입니다.

def sum_numbers(root):
    def dfs(node, num):
        if not node:
            return 0
        num = num * 10 + node.val
        if not node.left and not node.right:  # leaf
            return num
        return dfs(node.left, num) + dfs(node.right, num)

    return dfs(root, 0)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root))  # 12 + 13 = 25

root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2))  # 495 + 491 + 40 = 1026

빠른 확인

이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.

인터랙티브 레슨에서 답해보세요

수업 요약

이 수업에서는 경로 합의 변형(루트에서 리프까지의 경로, 모든 경로, 접두사 합을 사용하는 경로 합 III), 우아한 재귀적 분할을 이용한 최소 공통 조상, 그리고 순서 규칙을 사용해 O(log n)에 구하는 BST LCA를 배웠습니다. 다음에는 삽입 및 검색 작업으로 이진 탐색 트리를 시작합니다.

무료로 시작

AI 튜터와 함께 Python을(를) 배우세요 — 무료

브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.

코스
30
레슨
120
무료로 학습 시작전체 코스 보기

자주 묻는 질문

“경로 합과 최소 공통 조상” 강의는 무료인가요?

네 — “경로 합과 최소 공통 조상” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“경로 합과 최소 공통 조상”에서 뭘 배우나요?

재귀적으로 내려가며 일반 이진 트리의 root-to-leaf path sum, all-paths-sum, lowest-common-ancestor를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“경로 합과 최소 공통 조상” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. TreeNode 클래스와 레벨 순서 BFS
  2. 중위, 전위, 후위 DFS
  3. 지름, 높이, 균형 이진 트리
  4. 경로 합과 최소 공통 조상
← DSA Interview Prep(으)로 돌아가기