[Mock] Amazon 14

733. Flood Fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

My Answer 1: Accepted (Runtime: 72 ms - 83.98% / Memory Usage: 14.4 MB - 74.74%)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        def func(i, j, color):
            if i < 0 or i > len(image)-1 or j < 0 or j > len(image[0])-1 or image[i][j] != color:
                return
            
            image[i][j] = -1
            
            if i > 0 and image[i-1][j] == color:
                func(i-1, j, color)
            if i < len(image)-1 and image[i+1][j] == color:
                func(i+1, j, color)
            if j > 0 and image[i][j-1] == color:
                func(i, j-1, color)
            if j < len(image[0])-1 and image[i][j+1] == color:
                func(i, j+1, color)
            
        func(sr, sc, image[sr][sc])
        
        for i in range(len(image)):
            for j in range(len(image[0])):
                if image[i][j] == -1:
                    image[i][j] = newColor
        
        return image

원래 image[sr][sc] 컬러와 newColor 가 같은 경우는 무한으로 돌기 때문에

같은 컬러들은 우선 -1 값으로 통일해주고 마지막에 다시 newColor 로 바꿔줌

image 값들을 다시 보면서 newColor 로 바꿔주는게 뭔가 지저분한 거 같아서...
보니까 걍 if image[sr][sc] == newColor: return image 해주면 되는 거였음;
=> 그럼 func 에서 -1 로 할 필요없이 바로 newColor 로 넣어주기

---

1080. Insufficient Nodes in Root to Leaf Paths

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf. (A leaf is a node with no children.)

A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

My Answer 1: Accepted (Runtime: 136 ms - 9.39% / Memory Usage: 15.7 MB - 36.73%)

# 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 sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        def func(root, sums):
            if root is None:
                return 0
            
            # leaf 에서 sum 과 limit 비교
            if root.left is None and root.right is None:
                if sums+root.val < limit:
                    return 0    # 유효하지 X path
                else:
                    return 1    # 유효한 path
                
            a = func(root.left, sums+root.val)
            b = func(root.right, sums+root.val)
            
            if a == 0:
                root.left = None
            if b == 0:
                root.right = None
            
            # 왼,오 자식 모두 유효하지 않으면 부모도 잘라내기
            if a == 0 and b == 0:
                return 0
            else:
                return 1
        
        # 유효한 path 가 하나도 없으면 시작 root 도 잘라내야하므로 dummy 노드에 연결
        ans = TreeNode(0, None, root)
        
        func(ans, 0)
        
        # 유효한 path 가 하나도 없는 경우 return None
        if ans.right is None:
            return None
        
        return root

leaf node 에서 합과 limit 을 비교
=> 작으면 return 0 을 해줘서 부모 노드에서 잘라내도록 함

자식이 있는 부모들은 자식들을 모두 확인해서
0 인 자식은 다 잘라내고 둘다 0 일 경우는 부모 자신도 잘라내도록 return 0

유효한 path 가 하나도 없는 경우는 주어진 root 모두 잘라내야 하므로
dummy node 에 root 를 연결해서 시작

Solution 1: Accepted (Runtime: 212 ms - 5.31% / Memory Usage: 15.7 MB - 36.73%)

# 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 sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        if root.left == root.right:
            return None if root.val < limit else root
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        return root if root.left or root.right else None

limit 에 limit - root.val 를 넣어주기

if root.left == root.right: => leaf 노드 (둘다 None)
이 때, limit 과의 값 비교

왼, 오 자식 하나라도 있으면 return root
둘다 없으면 return None

간단하네..^^