Path Sum

Q: 경로 합의 시간 복잡도는 얼마인가요?

O(n) : 각 노드는 최대 한 번 방문하며, 일치하는 첫 번째 리프에서 탐색을 멈출 수 있습니다. 추가 공간은 탐색 중인 경로를 위한 O(h) 이며, 호출 프레임이나 직접 만든 스택의 항목으로 사용됩니다.

쉬움트리 순회

+10

레벨 순서대로 저장된 배열 tree와 숫자 targetSum이 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 각각 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있습니다. -1은 빈 위치를 나타내며, 배열 끝에 여분의 -1 항목이 있을 수 있습니다. 루트에서 리프까지 이어지는 경로 중 노드 값의 합이 targetSum과 같은 경로가 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 리프란 두 자식 위치가 모두 비어 있는 노드입니다.

함수

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: 레벨 순서로 이진 트리를 나타내며, 빈 위치는 -1로 표시합니다
targetSuminteger: 루트에서 리프까지의 경로가 도달해야 하는 총합
반환값boolean: 루트에서 리프까지의 경로 중 합이 targetSum이 되는 경로가 있으면 true, 그렇지 않으면 false

제약 조건

1 ≤ tree.length ≤ 32767
각 tree[i]는 -1이거나 0 ≤ tree[i] ≤ 1000을 만족하는 값입니다.
tree[0]은 절대 -1이 아니므로 트리에는 노드가 하나 이상 있습니다.
배열은 마지막 노드 뒤에 -1 항목이 추가로 있을 수 있습니다.
빈 칸의 두 자식도 모두 비어 있으며, 깊이는 최대 14입니다.
0 ≤ targetSum ≤ 15000

예제

입력: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
출력: true
설명: 경로 3, 9, 2(인덱스 0, 1, 4)의 합은 14이고, 인덱스 4의 2는 리프입니다.

입력: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
출력: false
설명: 3 + 9 = 12이지만, 9에는 자식 노드가 있으므로 어떤 경로도 그곳에서 끝나지 않습니다. 세 개의 루트-리프 경로의 합은 14, 10, 16이며, 그중 어느 것도 12가 아닙니다.

입력: tree = [4, -1, -1]targetSum = 4
출력: true
설명: 루트의 두 자식 위치가 모두 비어 있으므로 루트는 그 자체로 리프입니다. 4만 포함하는 경로의 합은 4입니다.

후속 질문

경로가 어떤 노드에서든 시작해 그 아래의 어떤 노드에서든 끝날 수 있다면, targetSum을 만드는 경로의 수를 셀 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

루트에서 리프까지 이어지는 전체 경로만 셉니다. 누적 합계가 아직 자식 노드가 있는 노드에서 targetSum에 도달할 수도 있지만, 이는 세지 않습니다. 따라서 경로의 합을 매개변수나 스택에 담아 모든 노드까지 전달하고, 리프에서만 목표값과 비교하세요.

남은 합에 대한 재귀

핵심 아이디어

targetSum와 합이 같은 경로는 루트의 값으로 시작하므로, 루트의 자식 중 하나에서 시작하는 나머지 경로의 합은 targetSum에서 그 값을 뺀 값이어야 합니다. 이는 더 작은 트리에서 같은 질문을 하는 것입니다. 내려가면서 각 노드의 값을 빼세요. 리프에서는 경로가 끝나므로, 남은 값이 없는지가 답입니다.

첫 번째 예제에서는 루트에서 14 - 3 = 11이 남고, 9에서 2가 남으며, 리프 2에서 0이 남습니다. 두 번째 예제에서는 9에서 이미 0이 남지만 자식이 있으므로 탐색을 계속합니다. 각 노드는 한 번씩 방문하므로 시간 복잡도는 O(n)이고, 호출 스택에는 레벨마다 프레임 하나씩, 최대 15개가 쌓입니다.

알고리즘

walk(i, remaining)를 작성하고 remaining에서 tree[i]를 뺍니다.
i의 두 자식 위치가 모두 비어 있으면(인덱스가 끝을 넘었거나 -1이면), remaining이 0인지 반환합니다.
그렇지 않으면 실제 왼쪽 자식 또는 실제 오른쪽 자식에 대해 walk를 호출한 결과가 true이면 true를 반환합니다.
walk(0, targetSum)을 반환합니다.

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

명시적 스택을 사용한 깊이 우선 탐색

핵심 아이디어

재귀는 호출마다 숫자 하나를 유지합니다. 대신 각 노드 옆의 스택에 직접 저장하세요. 루트에서 해당 노드까지 경로의 합입니다. (0, tree[0])에서 시작하세요. 각 자식은 부모의 합에 자신의 값을 더한 값을 받습니다. 쌍을 꺼내세요. 노드가 리프이고 합이 targetSum이면 완료입니다. 그렇지 않으면 실제 자식 노드를 넣으세요.

실제 노드는 각각 한 번씩 스택에 들어가므로 시간 복잡도는 O(n)이고, 스택에는 각 레벨마다 대기 중인 형제 노드 하나 정도가 저장되므로 O(h)입니다. 같은 반복문은 포인터 기반의 깊은 트리에서도 작동하며, 이 경우 재귀는 스택이 부족해질 수 있습니다.

알고리즘

(0, tree[0])을 스택에 넣습니다.
(i, total) 쌍을 꺼내고 자식 위치 2*i+1과 2*i+2를 살펴봅니다.
두 자식 모두 실제 노드가 아니고 total이 targetSum과 같으면 true를 반환합니다.
실제 자식 c를 각각 (c, total + tree[c])로 넣습니다.
스택이 비면 false를 반환합니다.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

함정과 경계 사례

모든 노드에서 합을 비교하기. 두 번째 예시에서 3 + 9 = 12는 자식이 있는 9에서 일치하므로 답은 false입니다.
빈 자식 자리가 경로를 끝내는 것을 허용하기. 그러면 두 번째 예시의 9는 비어 있는 왼쪽 자리를 통해 경로를 끝냅니다.
루트 노드만 있는 경우를 잊기. 노드 하나만 있어도 리프이므로, 목표값이 4인 [4]의 결과는 true이고, 목표값이 0인 [0]의 결과도 true입니다.
배열의 끝을 넘어 읽기. 끝부분에 가까운 리프의 자식 인덱스는 마지막 항목을 넘어갈 수 있습니다.
Lua와 R에서 오프셋을 혼동하기. 노드 인덱스는 2*i+1을 위해 0부터 시작하도록 유지하고 tree[i + 1]을 읽으세요.

자주 묻는 질문3

경로 합의 시간 복잡도는 얼마인가요?

O(n): 각 노드는 최대 한 번 방문하며, 일치하는 첫 번째 리프에서 탐색을 멈출 수 있습니다. 추가 공간은 탐색 중인 경로를 위한 O(h)이며, 호출 프레임이나 직접 만든 스택의 항목으로 사용됩니다.

Path Sum은 BFS로 풀 수 있나요?

네. 노드와 해당 노드까지의 경로 합으로 이루어진 쌍을 스택 대신 큐에 넣고, 꺼낼 때마다 각 리프 노드를 확인하세요. 시간 복잡도는 여전히 O(n)이지만, 큐에는 한 레벨 전체, 즉 완전 이진 트리 노드의 약 절반이 들어갈 수 있는 반면, 스택에는 레벨당 노드가 약 하나씩 들어갑니다.

목표값과 같아지는 모든 경로를 어떻게 찾나요?

내려가면서 현재 경로의 노드 목록을 유지하고, 합이 일치하는 각 리프에서 이를 답에 복사한 다음, 위로 돌아갈 때 마지막 노드를 제거하세요. 순회 방식은 그대로입니다. 일치하는 리프가 많으면 경로를 복사하는 데 순회보다 더 많은 비용이 들 수 있습니다.

def hasPathSum(tree, targetSum):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

예상 출력

true