Finding All Root-to-Leaf Paths with a Given Sum
[문제]
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
[입력 조건]
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
[추가 사항]
[내 풀이]
from typing import Optional, List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(node, currentSum, path):
if not node:
return
path.append(node.val)
currentSum += node.val
if not node.left and not node.right:
if currentSum == targetSum:
result.append(path[:])
dfs(node.left, currentSum, path)
dfs(node.right, currentSum, path)
# Backtrack
path.pop()
result = []
dfs(root, 0, [])
return result
[해결 방법]
🎯 문제 접근
이 문제는 이진 트리에서 루트 노드부터 리프 노드까지의 모든 경로를 탐색하며, 각 경로의 노드 값의 합이 주어진 targetSum과 같은지 확인하는 문제입니다.
🤔 접근 방법
DFS (깊이 우선 탐색)을 사용하여 트리의 모든 경로를 탐색합니다.
각 노드를 방문할 때마다 현재 경로에 해당 노드의 값을 추가하고, 현재 경로의 합계를 업데이트합니다.
리프 노드에 도달했을 때, 현재 합계가 targetSum과 일치하면, 해당 경로를 결과 리스트에 추가합니다.
백트래킹을 사용하여, 탐색이 끝난 후에는 현재 노드를 경로에서 제거합니다. 이렇게 하면 다른 경로를 탐색할 때 이전 경로의 값이 남아있지 않게 됩니다.
💡 해결 과정
트리가 비어 있는 경우, 즉 루트가 None인 경우, 바로 빈 리스트를 반환합니다.
리프 노드에 도달할 때까지 DFS를 사용하여 왼쪽과 오른쪽 자식 노드를 재귀적으로 탐색합니다.
경로를 탐색하는 동안 경로의 합이 targetSum과 일치하면 결과 리스트에 추가합니다.
😊 배운 점
이 문제를 해결하면서 DFS와 백트래킹의 중요성을 다시 한번 느꼈습니다. 트리 구조에서 모든 경로를 탐색해야 하는 문제에서는 DFS가 매우 유용한 점, 특히 백트래킹 기법을 사용하면 메모리 사용을 최소화하면서 효율적으로 해결할 수 있다는 점을 알게되었습니다.
