[leetcode] 112. Path Sum

원문)

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.

번역)

이진트리와 합계가 주어졌을때,
root부터 leaf까지 경로의 값을 모두 더했을때 나오는 값과 주어진 합이 같을때의
경로가 있는지 구하라.


예제)

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

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

문제접근)

1. 접근

• 접근은 다 맞았는데 root is None check에서 고생했다.
  생각해보면 leaf노드만 체크해야한다.
  [1,2] 1의 경우를 생각해보면 된다.

코드)

1.접근

# 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:
        return self.top_down(root, sum)
    
    def top_down(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False
        elif root.val == sum and root.left is None and root.right is None:
            return True

        sum -= root.val
        l = self.top_down(root.left, sum)
        r = self.top_down(root.right, sum)
        return l or r

# 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:
        stack = [(root, sum)]
        
        while stack:
            cur, s = stack.pop()
            if cur:
                if cur.val == s and cur.left is None and cur.right is None:
                    return True
                
                s -= cur.val
                stack.append((cur.left, s))
                stack.append((cur.right, s))
        return False