5 posts tagged with "Depth-First Search"

class Solution:
    def numIslands(self, grid) -> int:
        M, N = len(grid), len(grid[0])

        def dfs(m, n):
            r = 0 <= m < M and 0 <= n < N and grid[m][n] == '1'
            if r:
                grid[m][n] = None
                list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))
            return r

        return sum(dfs(m, n) for m in range(M) for n in range(N))

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


class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        return root

class Solution:
    def floodFill(
        self, image: list[list[int]], sr: int, sc: int, color: int
    ) -> list[list[int]]:
        COLOR, M, N = image[sr][sc], len(image), len(image[0])

        def dfs(m, n):
            if not all([0 <= m < M, 0 <= n < N]):
                return

            if not all([image[m][n] == COLOR, image[m][n] != color]):
                return

            image[m][n] = color
            list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))

        dfs(sr, sc)
        return image

# 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 isValidBST(self, root, lo=float('-inf'), hi=float('inf')) -> bool:
        '''
        [5,4,6,null,null,3,7] => false
        '''
        return (not root) or all(
            [
                lo < root.val < hi,
                self.isValidBST(root.left, lo, root.val),
                self.isValidBST(root.right, root.val, hi),
            ]
        )

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""


class Solution:
    def preorder(self, root):
        return (
            (root.val,) + sum((self.preorder(x) for x in root.children), ())
            if root
            else ()
        )