•
문제 링크 : 
LeetCodePath Sum - LeetCode
•
문제 설명 : 제공된 트리가 Root → Leef 노드까지 경로에 존재하는 모든 노드의 val을 합쳤을 때, targetSum을 만들 수 있는 경로가 있는지 반환
•
풀이 방법
◦
DFS를 통해, Leef 노드까지 탐색 후 targetSum과 동일한지 비교하였다.
◦
하위로 내려가면서, 현 노드의 값을 누적하며 Sum을 만들었다.
•
시간복잡도 :
•
성공 코드
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def search_tree(node, current_sum):
# 현 노드가 Leef 노드이며, root -> leef 노드까지의 합이 targetSum 인지 여부
if not node.left and not node.right and current_sum + node.val == targetSum:
return True
# 아니라면 하위 탐색
left = search_tree(node.left, current_sum + node.val) if node.left else False
right = search_tree(node.right, current_sum + node.val) if node.right else False
return left or right
# Root 노드가 존재
if root:
# 좌/우 하나라도 하위 트리가 있다면 탐색
if root.left or root.right:
left = search_tree(root.left, root.val) if root.left else False
right = search_tree(root.right, root.val) if root.right else False
return left or right
# Root 노드만 존재하는 경우
else:
return root.val == targetSum
# Root 노드도 없는 빈 트리일 경우
else:
return False
Python
복사