Leetcode patterns — BFS

def bfs():
q = [start_nodes]
while q:
nexts = []
while q:
n = q.pop(0)
result= do_something(n)
nexts.extend(next_level_nodes(n))
q = nexts
return result

BFS with Tree

def bfs(root):
q= [root]
res=[]
res.append([root.val])
while q :
child=[]
while q:
n = q.pop(0)
# do something to current
if n.children:
child.extend(n.children)
if child:
# do something to children
q=child
return res
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
q= [root]
res=[]
res.append([root.val])
while q :
child=[]
while q:
n = q.pop(0)
if n.children:
child.extend(n.children)
if child:
res.append([x.val for x in child])
q=child
return res
def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
"""
Case1 : insert at root
Case2 : insert at last row
Case3 : insert betwwn first and last row
"""
if not root:
return []

if depth == 1: # Case1
return TreeNode(val, root)
q = [root]
last_row = []
d=1
def insert(n, val):
left, right = n.left, n.right #original left and right
n.left = TreeNode(val, left=left) #left=new_node, new_node'left = original left
n.right = TreeNode(val, right=right)#right=new_node, new_node'right = original right
return n
while q:
if d == depth-1: # Case3
for n in q:
n=insert(n, val)
return root
else:
child = []
while q:
n = q.pop(0)
if n.left:
child.append(n.left)
if n.right:
child.append(n.right)
q = child
if q:
last_row = q
d+=1
for n in last_row: # Case2
n=insert(n, val)
return root

BFS with metrix

def orangesRotting(self, grid: List[List[int]]) -> int:
# load the rotten into q
q = []
row, col = len(grid), len(grid[0])
for r in range(row):
for c in range(col):
if grid[r][c] == 2:
q.append((r,c))
# find the neighbor oranges which could get rotten in next time
def get_next(r,c):
d = [(1,0),(0,1),(-1,0),(0,-1)]
nonlocal grid, row, col
res = set()
for d1 in d:
r1,c1 = r+d1[0], c+d1[1]
if r1 < 0 or c1 < 0 or r1 == row or c1 == col or grid[r1][c1] != 1:
continue
res.add((r1,c1))
return res
# BFS rotten the next
res = 0
while q:
nexts = set()
for r,c in q:
grid[r][c]=2
while q:
r,c = q.pop()
nexts|=get_next(r,c)
q = nexts
if not q: # handle last day
break
res+=1
# all must be rotten then consider success
for r in range(row):
for c in range(col):
if grid[r][c] == 1:
return -1
return res

BFS with key-value mapping

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store