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"
Top comments (0)