Path Sum
레벨 순서대로 저장된 이진 트리 배열 tree와 숫자 targetSum이 주어집니다. 루트는 인덱스 0에 있고, 인덱스 i에 있는 노드의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, -1은 비어 있는 위치를 나타내고, 배열은 끝에 여분의 -1 항목을 포함할 수 있습니다. 루트에서 리프까지 이어지는 경로 중 값의 합이 targetSum인 경로가 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 리프는 자식이 없는 노드입니다. 즉, 두 자식 위치가 모두 비어 있습니다.
함수
- 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입니다.
제출 시 숨은 테스트 +14개
후속 질문
경로가 루트에서 리프까지 이어지는 경우뿐 아니라 어떤 노드에서든 시작해 그 아래의 어떤 노드에서든 끝날 수 있을 때, targetSum이 되는 경로의 수를 셀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
루트에서 아래로 내려가며 누적 합계를 계속 계산하세요. 그 합계를
targetSum과 비교해도 되는 지점은 어디인가요?리프에서만 해당합니다. 리프란 두 자식 자리가 모두 비어 있는 노드입니다. 자식이 하나 있는 노드는 합계가 이미 일치하더라도 경로의 끝이 아닙니다. 지금까지의 경로 합계를 각 자식에게 전달하세요.
쌍으로 된 항목의 스택을 유지합니다. 각 쌍에는 노드 인덱스와 루트에서 해당 노드까지의 합이 들어 있습니다. 쌍을 꺼냅니다. 노드가 리프이고 합이
targetSum과 같으면true를 반환합니다. 그렇지 않으면 실제 자식 노드마다 자식의 값만큼 합을 더해 스택에 넣습니다.
풀이
이 문제는 루트에서 리프까지 이어지는 전체 경로에 관한 것입니다. 누적 합이 경로 중간에 targetSum에 도달하더라도, 해당 노드에 아직 자식 노드가 있다면 조건에 맞지 않습니다. 따라서 지금까지 경로의 합을 각 노드에 전달하고, 리프에서만 목표 합과 비교해야 합니다. 재귀에서는 그 합을 매개변수로 전달하고, 스택에서는 각 노드와 함께 합을 저장합니다.
남은 합에 대한 재귀
핵심 아이디어
먼저 배열에서 이동하는 방법을 알아봅시다. 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1에, 오른쪽 자식은 2*i+2에 있습니다. 자식은 해당 인덱스가 배열 범위 안에 있고 그 위치의 값이 -1이 아닐 때만 실제로 존재합니다. [3, 9, 6, -1, 2, 1, 7]에서 루트 3의 자식은 인덱스 1과 2에 있고, 인덱스 1의 9는 왼쪽 위치 3이 비어 있으며 오른쪽에는 인덱스 4의 2가 있습니다.
이제 핵심 아이디어를 살펴봅시다. 합이 targetSum인 경로는 루트의 값에서 시작하므로, 루트의 자식 중 하나에서 시작하는 나머지 경로의 합은 targetSum에서 루트의 값을 뺀 값이어야 합니다. 이것은 더 작은 트리에서 같은 질문을 하는 것과 같습니다. 내려가면서 각 노드의 값을 빼세요. 리프에서는 경로가 끝나므로, 남은 값이 없는지가 답입니다.
첫 번째 예에서 루트를 거치면 14 - 3 = 11이 남고, 9를 거치면 2가 남으며, 리프 2를 거치면 0이 남습니다. 따라서 true입니다. 두 번째 예에서 9를 거치면 이미 0이 남지만, 자식이 있으므로 탐색을 계속하고 그 리프에서는 -2가 남습니다. 각 노드는 최대 한 번 방문하므로 시간 복잡도는 O(n)이고, 호출 스택에는 레벨마다 프레임 하나가 유지되므로 O(h)이며, 여기서는 최대 15개의 프레임입니다(깊이가 14라면 루트 아래의 간선이 14개라는 뜻입니다).
알고리즘
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과 같으면 끝입니다. 그렇지 않으면 실제 자식 노드를 스택에 넣습니다. 첫 번째 예시에서는 오른쪽 부분이 스택에서 먼저 나옵니다. 리프 7과 1은 각각 16과 10을 가집니다. 그런 다음 9에 해당하는 (1, 12)가 나옵니다. 리프가 아니므로 올바른 합을 가진 리프인 (4, 14)를 스택에 넣습니다.
실제 노드는 각각 한 번씩만 스택에 들어가므로 시간 복잡도는 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입니다. 리프에서만 비교하세요. - 비어 있는 자식 자리를 경로의 끝으로 취급합니다. 비어 있는 자리에서
walk가remaining == 0을 반환하면, 두 번째 예제의9는 왼쪽 자리가 비어 있다는 이유로 리프로 계산됩니다. 노드는 양쪽 자리가 모두 비어 있을 때만 리프입니다. - 루트 노드만 있는 경우를 잊습니다. 노드 하나만 있어도 리프이므로,
targetSum = 4인[4]는true이고targetSum = 0인[0]도 그렇습니다. - 합계가 목표값을 넘으면 탐색을 중단합니다. 여기서는 값이 음수가 될 수 없으므로 이 문제에서는 안전하지만, 트리에 음수 값이 들어갈 수 있는 순간 같은 코드는 오답을 냅니다.
- 배열의 끝을 넘어 읽습니다. 배열은 마지막 노드 바로 뒤에서 끝날 수 있으므로, 배열 끝에 가까운 리프의 자식 인덱스가 마지막 항목을 넘어갈 수 있습니다.
tree[c]를 읽기 전에 인덱스를 확인하세요. - 배열 인덱스가 1부터 시작하는 Lua와 R에서 오프셋을 혼동합니다.
2*i+1계산에는 노드 인덱스의 0 기반 방식을 유지하고,tree[i + 1]을 읽으세요.
자주 묻는 질문4
Path Sum의 시간 복잡도는 얼마인가요?
각 노드는 최대 한 번 방문하므로 시간 복잡도는 O(n)이고, 조건에 맞는 첫 번째 리프에서 탐색을 멈출 수 있습니다. 추가 공간은 탐색 중인 경로에 대해 O(h)이며, 호출 프레임이나 직접 만든 스택의 항목으로 저장됩니다.
Path Sum은 왜 리프 노드에서만 합계를 확인하나요?
이 문제는 루트에서 리프까지의 경로를 요구하며, 자식이 있는 노드에서 멈추는 경로는 해당하지 않습니다. 모든 노드에서 확인하면 true를 너무 자주 반환합니다. 예를 들어 루트의 값만으로도 목표값과 같지만 루트에 자식이 있는 경우가 그렇습니다. 노드는 두 자식 위치가 모두 비어 있을 때만 경로의 끝이 됩니다.
Path Sum을 BFS로 해결할 수 있나요?
네. 노드와 그 경로 합으로 이루어진 쌍을 스택 대신 큐에 넣고, 각 리프 노드가 꺼내질 때 확인하세요. 시간 복잡도는 여전히 O(n)이지만, 큐에는 한 레벨 전체, 즉 완전한 트리 노드의 약 절반이 들어갈 수 있는 반면, 스택에는 레벨당 노드가 약 하나씩 들어갑니다.
목표값이 되는 모든 경로를 어떻게 찾나요?
내려가면서 현재 경로에 있는 노드 목록을 유지하고, 합이 일치하는 각 리프에서 그 목록을 답에 복사한 다음, 다시 올라갈 때 마지막 노드를 제거하세요. 순회는 그대로이고, 기록 관리만 늘어납니다. 일치하는 리프가 많으면 경로를 복사하는 데 순회 자체보다 더 많은 비용이 들 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def hasPathSum(tree, targetSum):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
tree = [3, 9, 6, -1, 2, 1, 7] targetSum = 14
기대값
true