본문 바로가기
코딩 공부

Leetcode Path Sum Python 풀이

by 카우보이연구소 2022. 1. 24.

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Path Sum
등급: Easy

이것도 나에게는 왜 이렇게 어려운지.

<코드>

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        
        if not root.left and not root.right and root.val == targetSum:
            return True
        
        targetSum -= root.val
        
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

Recursive, 재귀 호출 함수다. 

 

간단하게, 일단 root가 null이면 당연히 False를 반환한다. 

 

다음 if는 마지막 node인지를 확인하고 (not root.left and not root.right), root.val가 sum인지를 확인한다. sum == root.val라면 True가 반환된다. 그런데 어떻게 sum == root.val인가?

 

왜냐하면 재귀호출을 통해 targetsum -= root.val가 되기 때문이다. node 하나씩 지나갈 때마다 그 node.val를 빼게 되어있다. 

 

그리고 각 node마다 node.left and node.right의 haspathsum()이 재귀호출이 되기 때문에 targetsum은 각 node마다 다름으로 걱정을 안 해도 된다.

 

또한, iterative 방식도 있다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        stack = [(root, targetSum)]
        
        while stack:
            node, sum = stack.pop()
            
            if not node:
                continue
            
            if not node.left and not node.right and node.val == sum:
                return True
            
            stack.append((node.right, sum-node.val))
            stack.append((node.left, sum-node.val))
            
        return False

다른 많은 tree 방식과 같이 stack에 세트를 활용하는 방법이다. 논리는 위의 recursive 코드와 같다.

<오류, 힘들었던 점>

언제나쯤 이런 게 생각만 하면 나오려나.

 

<총평>

 

Happy coding!

 

Path Sum - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

댓글