LeetCode/Path Sum

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 코 m/p로 b㎇ms/파 th-스 m/ ]

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values ​​along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

binary tree의 끝에서 끝까지의 root-to-leaf의 합계 값이 변수 sum의 값과 일치하는 부분이 있는지 여부를 판단하는 문제입니다.

해답·해설

해법 1

recursive를 사용한 해법.
recursive에 root의 값을 따라갈 때 sum -= root.val로 sum을 줄이고, sum == root.val이 되면 True를 반환한다. 일단 False를 반환한다는 처리.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right and root.val == sum:
            return True
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

해법 2

Iterative 해법.
Iteration을 돌리는 과정에서 (root, root.val)의 튜플 형식으로 변수 stack에 저장하면서 curr, val = stack.pop()로 먼저 stack에 저장된 튜플을 꺼내 val이 sum 동일한 값인지 여부를 결정합니다.

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        stack = [(root, root.val)]
        while stack:
            curr, val = stack.pop()
            if not curr.left and not curr.right:
                if val == sum:
                    return True
            if curr.right:
                stack.append((curr.right, val+curr.right.val))
            if curr.left:
                stack.append((curr.left, val+curr.left.val))
        return False