[LeetCode] 112. Path Sum

112. Path Sum

Easy

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

 

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

---

문제 풀이

• 이진 트리이며 꼭대기 노드부터 마지막 노드까지의 숫자의 합이 targetSum 과 같은지 알아내야한다.
• 시작점과 끝점이 항상 root 부터 leaf 이며, 이는 마지막 노드의 자식들이 존재하지 않아야한다. 
• 제한을 확인했을때 노드의 총 갯수는 5000 개 이므로 이진탐색으로 모든 노드를 검색해도 O(N) 시간이 걸릴 것이다. 
• 그래서 재귀함수로 풀되 종료 조건을 조심해야한다. 
• 처음 루트부터 값을 더해 나가고, 마지막 정답을 확인할때 자식들이 없는지 확인해야한다. 
• 리턴하는 정답 처리는, 더 이상 노드가 존재하지않으면 False 를 리턴하고
• 자식들이 없을때 노드 값들의 합이 정답과 같으면 True 를 리턴한다. 
• 즉 리턴을 해줄때, or 연산을 해주면 어디 하나라도 True 가 존재하면 계속 해서 True 를 리턴하기 때문에 정답을 리턴 받을 수 있다. 

소스 코드

# 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 rec(node, target):
            if not node:
                return False
            
            currTar = target - node.val

            if currTar == 0 and not node.left and not node.right:
                return True
                        
            return rec(node.left, currTar) or rec(node.right, currTar)
        return rec(root, targetSum)