DFS and BFS

Today I will start refreshing my computer science knowledge by writing tech blogs.

Start from Leetcode 865.
It's exactly same with Leetcode 1123

read the question clearly before starting coding, I thought there was only one deepest node in the tree, so I didn't think this was a problem of the LCA. the key to solving this problem is to check the left and right subtrees if they have the same level, if yes that means their parent is the smallest subtree. There are two conditions: a) when the 2 nodes are at the same deepest level, then their parent node is the smallest subtree.

b) if there is only one node is the deepest level, then it self is the smallest subtree

The first way I can think of is recursive, here is the code:

class Solution:
    max_level = 0
    res = None

    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        level = 0
        self.dfs(root,level)
        return self.res


    def dfs(self,node,current_level):
        if not node:
            return current_level
        else:
            l_next_level = self.dfs(node.left,current_level+1)

            r_next_level = self.dfs(node.right,current_level+1)

            max_cur_level = max(l_next_level,r_next_level)

            self.max_level = max(self.max_level,max_cur_level)

            if self.max_level == l_next_level and self.max_level==r_next_level:
                self.res = node

            return  max_cur_level

Since we need to keep track of the same level of the deepest nodes and find their common ancestor, it seems hard to simulate it with a iterative dfs, if you can, please leave the comment.

I try to use BFS to solve the same problem:

    def bfs(self,node):
        leftmost_node = None
        rightmost_node = None
        q = [node]
        while q:
            q_size = len(q)
            for i in range(q_size):
                the_node = q.pop()
                if i == 0:leftmost_node = the_node
                if i == q_size - 1 : rightmost_node = the_node
                if the_node.left: q.insert(0,the_node.left)
                if the_node.right:q.insert(0,the_node.right)
        self.res = self.lca(node,leftmost_node,rightmost_node)
        return 
    def lca(self,root,p,q):
        if not root:return
        if root==p or root ==q: return root
        left = self.lca(root.left,p,q)
        right = self.lca(root.right,p,q)
        if not left:
            return right
        elif not right:
            return left
        else:
            return root

Based on this problem, let's explore more about dfs and bfs.

Let's see Leetcode 200
This is a classic problem that can be solved by dfs and bfs. For dfs, the idea is we need to start from all points on the map and explore all the islands that can be reached. The basic operation is to check the four directions around the point to see if there are "1", if yes go into that point and check its four directions, and repeat this until no "1" is found around. Here is the code:

class Solution:
    directions = [
        [0,1], #right
        [1,0], #down
        [-1,0],#up
        [0,-1],#left
    ]
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    grid[i][j] = "0"
                    count += 1
                    self.dfs(grid,i,j)
        return count


    def dfs(self,grid,i,j):
        for m,n in self.directions:
            if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1":
                grid[i+m][j+n] = "0"
                self.dfs(grid,i+m,j+n)

In this code, we changed the visited points in place to "0", if we don't want to change the the given grid, we can also store the visited points like this:

    def numIslands_no_self(self, grid: List[List[str]]) -> int:
        def dfs(i,j):
            visited.add((i, j))
            for m,n in self.directions:
                if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1" and (i+m,j+n) not in visited:
                    dfs(i+m,j+n)

        if not grid or not grid[0]: return 0    
        visited = set()        
        count = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                print(54,visited)
                if grid[row][col] == "1" and (row,col) not in visited:
                    count += 1
                    dfs(row,col)

        return count

You may wonder why I named the function "no_self". At the very beginning, I used a global variable to save the visited points, logically speaking, it's no different from the local variable, but when I submitted it, it couldn't pass the test. I figured that caused by the global variable is long-lived in memory, when a new test case comes in, the old visited points are still there, and that's why it cannot go through. So I recommend we all use the local variable here.

Next, I will try to use BFS to solve the problem. The key of BFS will queue, and iteration will be like the wave spread from the middle.

    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs():
            if not grid or not grid[0]: return 0
            count = 0
            q = []
            for row in range(len(grid)):
                for col in range(len(grid[0])):

                    if grid[row][col]=="1":
                        count += 1
                        q.insert(0,(row,col))


                    while q:
                        i,j = q. pop()
                        if grid[i][j] == "1":
                            grid[i][j] = "0"
                            for m,n in self.directions:
                                if  0<= i+m < len(grid) and 0<= j+n <len(grid[0]) and grid[i+m][j+n] == "1":
                                    q.insert(0,(i+m,j+n))
            return count
        return bfs()

Let's try another one Leetcode 130
the key to this problem is to find all O at the edge of the board and all O connected to them cannot be converted. All other O needs to convert to X, here is the implementation:

class Solution:
    directions = [
        [0,-1],
        [0,1],
        [1,0],
        [-1,0]
    ]
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(i,j):
            if board[i][j] in ["#","X"]: return
            board[i][j] = "#"
            for m,n in self.directions:
                if 0 <= i+m <len(board) and 0<= j+n <len(board[0]):
                    dfs(i+m,j+n)



        if not board or not board[0]: return
        for i in range(len(board)):
            for j in range(len(board[0])):
                if i == 0 or i == len(board) - 1 or j == 0 or j == len(board[0]) - 1:
                    dfs(i,j)

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "#":
                    board[i][j] = "O"

Blog

Einsteinder

Join Our Newsletter. No Spam, Only the good stuff.

Related