LeetCode 112(Path Sum, Python)

1. 문제 링크

• https://leetcode.com/problems/path-sum/

Path Sum - LeetCode

2. 문제 설명

• 이진 트리 root와, 정수 targetSum가 주어졌을 때,
• root에서 leaf로 이어진 path의 node합이 targetSum과 동일한게 존재하면 True, 그렇지 않으면 False 반환
  • 여기서 leaf란 자식이 없는 node를 의미 
• 예시) targetSum=22
  • 아래처럼 이진 트리가 주어졌을 때, 5+4+11+2=22로 targetSum과 동일한 root-leaf node합이 존재하므로 True 반환
  •         5
           / \
          4   8
         /   / \
        11  13  4
       /  \      \
      7    2      1

 

3. 처음 풀이

• 가장 위에 노드와 node.left, node.right만 있다고 생각하고, 언제 재귀가 끝날 수 있는지를 생각하니, 문제가 조금 편해졌다. 
• 재귀가 언제 True일까? 
  • targetSum에서 root.val을 뺀게 0이거나, root.left와 root.right 둘다 Null이면 True가 반환된다
• targetSum에서 root.val 뺀 값이 0이 될때까지 반복해야 하므로, root가 None이면 재귀가 끝나면 안되니 False 반환
• 그 이외의 경우는?
  • root의 왼쪽 노드, root의 오른쪽 노드를 탐색한다. 
  • 여기서 핵심은 →targetSum을 업데이트 해주는 것. targetSum을 targetSum - root.val로 업데이트 해줘야, node.left, node.right를 다시 root node로 간주하고 재귀가 돌 수 있음

# 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:
        if root is None:
            return False
        elif targetSum - root.val == 0 and root.left is None and root.right is None:
            return True
        else:
            return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

4. 다른 풀이

• 제로_콜라가 푼 풀이 
• checkSum이라는 함수를 두어, 해당 함수에서, 현재 노드에서 시작해서 모든 가능한 경로의 합을 계산해둠. 
• 최종적으로 targetSum이 checkSum(모든 경우의 수 집합)에 포함되고 있으면 True를, 그렇지 않으면 False를 반환

# 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 checkSum(root):
            if not root:
                return []
            elif not root.left and not root.right:
                return [root.val]
            else:
                return [x + root.val for x in checkSum(root.left)+checkSum(root.right)]
        return targetSum in checkSum(root)

5. 배운점

• 재귀로 풀 때는, 전체 트리 구조를 생각하지 않고, root, root.left, root.right 세가지만 보면서 언제 재귀가 멈추게 될지 판단해보기!