[1스4코2파] # 161. LeetCode Pattern 112. Path Sum

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (161차)
[4코1파] 2023.01.13~ (153일차)
[1스4코1파] 2023.04.12~ (64일차)
[1스4코2파] 2023.05.03 ~ (43일차)

Today :

2023.06.12 [161일차]
LeetCode Patterns
112. Path Sum
https://leetcode.com/problems/path-sum/

112. Path Sum

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

문제 설명

binary tree와 target이 주어졌을때, 노드에서 leaf 노드 까지의 합들이 target과 같은 값이 있는지 없는지 확인하는 것
있으면 True, 없으면 False 를 return함

문제 풀이 방법

일단 정점에서 leaf node 까지 움직이면서 합을 구해야겠지..
합을 구하면서 target과 비교해서 target보다 합이 넘어가면 backtracking 하는 것도 생각했지만 그정도까지는 아닌 것 같아서 그냥 노드에 있는 합을 구하고
그게 있으면 True, 없으면 False를 return 했다

내 코드

(1) queue 를 이용한 dfs

from collections import deque

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: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
        queue = deque([(root, root.val)])
        
        while queue:
            node, val = queue.popleft()
            if not node.left and not node.right:
                if val==targetSum:
                    return True
                else:
                    continue

            if node.left:
                queue.append((node.left, val+node.left.val))

            if node.right:
                queue.append((node.right, val+node.right.val))
                                 
        return False

(2) 재호찬스 쓴 recursion

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: TreeNode, targetSum: int) -> bool:

        def dfs(root, cnt):
            if not root:
                return False

            cnt +=  root.val
            if not root.left and not root.right:
                return cnt == targetSum

            return dfs(root.left, cnt) or dfs(root.right, cnt)
        
        return dfs(root, 0)

증빙

이거 deque

이거 recursion

여담

배 곱 하